比赛（gaming）

题目描述

⼀年⼀度的校园歌⼿⼤赛开始了，今年⼀共有$n$个选⼿参与了⽐赛，分别编号为$1到n$ ，每 个⼈的唱功可以⽤数字$a_i$来量化，保证$a_1到a_n$互不相同。

今年赛事委员会决定让⽐赛变得更刺激⼀点，于是采⽤了以下的赛制：

编号为$2d+1$的选⼿和编号为$2d+2$的选⼿会通过对唱来PK（$d$ 为整数），唱功更 ⾼的选⼿（即$a_i$更⼤的选⼿）获胜，晋级下⼀轮。如果$n$为奇数，则编号为$n$的选⼿ 轮空，直接晋级。这⼀轮所有淘汰的选⼿，其最终名次就是第$\left \lceil \frac{n}{2}+1 \right \rceil$名。

所有晋级的选⼿重新编号$1到\left \lceil \frac{n}{2}\right \rceil$，继续下⼀轮。

直到剩下⼀个选⼿，Ta就是歌⼿⼤赛的冠军，其名次也就是第$1$ 名。

唱功不错的⼩ B 却惨遭⼀轮游，原因是第⼀轮遇到的对⼿最后获得了冠军。 所以他为了向赛事委员会说明这个⽐赛规则的不合理性，他想对于每⼀个$i$，求出如果初始编 号为$i$的选⼿能在第⼀次被淘汰的那⼀场⽐赛获胜晋级，他最终能得到什么名次。

输入格式

第 ⾏包含⼀个正整数$n$，表⽰选⼿数量。

第 ⾏包含$n$个正整数$a_1,a_2,...,a_n$ 表⽰每⼀位选⼿的唱功。

输出格式

包含⼀⾏$n$个整数，含义如题。

样例 #1

样例输入 #1

10
3 9 6 12 15 24 30 18 27 21

样例输出 #1

4 3 4 2 4 2 1 4 1 2

提示

样例解释

第⼀轮选⼿$\left [ 3，9，6，12，15，24，30，18，27，21 \right ]$

第⼆轮$\left [ 9，12，24，30，27\right ]$

第三轮$\left [ 12，30，27 \right ]$

第四轮$\left [ 30，27 \right ]$

第五轮$\left [ 30 \right ]$

对于选⼿$2$，他第⼀次被淘汰在第⼆轮，若获胜，则第三轮选⼿是$\left [ 9,30,27\right ]$，所以选⼿$2$ 最后的名次变成了$3$。

数据范围 对于所有数据 $n≤5×10^5,a_i≤10^9$,并且互不相同。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n;
int a[N],b[N];
map<int,int> mp,mp1;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		mp[a[i]]=i;
	}
	for(int i=1;i<=n;i++) b[i]=a[i];
	for(int i=1;i<=n;i++)
	{
		int num=n;
		bool pd=false;
		for(int j=1;j<=n;j++)
		{
			a[j]=b[j];
		}
		bool pd1=false;
//		cout<<a[i]<<"---\n";
		while(num>1)
		{
			int cnt=0;
			pd1=false;
			for(int j=1;j<=num;j+=2)
			{
				if(a[j]==b[i]||a[j+1]==b[i])
				{
//					cout<<pd<<"\n";
					if(b[i]>a[j]||b[i]>a[j+1])
					{
						a[++cnt]=b[i];
					}
					else if(!pd)
					{
							pd=true;
							a[++cnt]=a[j];
							a[++cnt]=a[j+1];
					}
					else
					{
						pd1=true;
						cout<<num/2+1<<" ";
						break;
					}
				}
				else
				{
					a[++cnt]=max(a[j],a[j+1]); 
				}
			}
//			cout<<"\n";
//			for(int j=1;j<=cnt;j++) cout<<a[j]<<" ";
//			cout<<"\n";
			if(pd1)
			{
				break;
			}
			if(num%2==1) a[++cnt]=a[num];
			num=cnt;
		}
		if(!pd1) cout<<1<<" ";
	}
}