有n个人在排队买票，队伍的位置为1到n。

给你一个数组a[i]， 其中第i个人想要买a[i]张票。

每一秒，位于队列头的人一次可以买一张票。如果他这次买完了所有他需要的票，他就会离开否则，它会来到队伍末尾继续排队。

现在给出所有人需要的票数，需要你求出每个人买完票的时间。（第一个人买完第一张票算作第一秒）。

输入格式

第一行一个整数n。

接下来一行一个长度为n的字符串s(就是输入n个数字)。

输出格式

输出n个数，第i个数表示第i个人买完票的时间。

样例输入

4
3 4 2 1

样例输出

8 10 7 4

数据规模

对于所有数据，保证n≤1000, 1≤a[i]≤1000。

答案

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e6+5;                    //由题意可得最多1000个人，每个人最多进队1000次，那么队列至少需要开1e6这么大
int Queue[N], front=1, rear=0;
int count[1005], Time[1005];            //count记录每个人还需要多少票，Time记录需要的时间

int main(){
	
	int n;
	scanf("%d", &n);
	for(int i=1; i<=n; i++){
		scanf("%d", &count[i]);        //每个人初始的买票数量
		Queue[++rear] = i;             //初始的买票顺序来依次进队
	}
		
	
	while(front <= rear){            //当front>rear队列为空，即所有人都买完票后就终止循环
		
		count[Queue[front]]--;       //买1张票就减1，队列中的是有那些人还需要买票
		
		if(count[Queue[front]] == 0)
			Time[Queue[front]] = front;    //此时的front就是该人买完票所需要的总时间
		else
			Queue[++rear] = Queue[front];    //没买完票就重新进队
		
		front++;           //该下一个人买票了
	}
		
	for(int i=1; i<=n; i++)
		printf("%d ", Time[i]);
	
	return 0;
}