彩虹
时间限制： 1.0 秒
空间限制： 512 MB
相关文件： 题目目录
题目描述
琦琦有很多颗彩虹糖，每一颗彩虹糖有一个美味度（是不超过 109 的非负整数），不同的彩虹糖可能有相同的美味度。
初始时，琦琦将所有的彩虹糖排成一个环，并会依次告诉你环上每颗糖的美味度。之后的每秒钟，琦琦会找出美味度极大的若干颗彩虹糖，并把它们同时吃掉。“极大”在这里指：如果某颗糖的美味度同时大于等于与它相邻的两颗糖的美味度，则认为这颗糖为美味度极大。（注：如果在某个时刻仅剩两颗糖，则这两颗糖互为相邻；如果在某个时刻仅剩一颗糖，则它“相邻的两颗糖”均为自己，从而这颗糖在这秒钟一定会被吃掉。）
容易发现，最终的情况一定是所有的糖都被吃掉了，而不会有剩余。琦琦想知道，每颗糖是在第几秒被吃掉的？
琦琦还要忙着去给乔乔买棒棒糖吃，这么简单的任务当然就交给你来完成啦！
输入格式
从标准输入读入数据。
第一行输入一个整数 n，表示彩虹糖的数量。
第二行输入 n 个空格隔开的整数，依次表示每颗彩虹糖的美味度。注意：所有的彩虹糖形成了一个环，第一个与最后一个输入的彩虹糖初始时也是相邻的。
输出格式
输出到标准输出。
输出 n 行，每行一个整数，依次表示每颗糖是在第几秒被吃掉的。
样例1输入
7
1 3 2 4 2 3 1
样例1输出
3
1
2
1
2
1
3
子任务
非公开与公开数据各 10 个测试点，分布相同。每 10 个测试点中的 n 分别为：
1000
2000
5000
10000
20000
50000
100000
200000
500000
1000000
提示
请自己设计高效完成此题所需的数据结构，例如数组、链表、栈、队列、优先队列等。
本题可能有多种不同的解题思路。
有些解题思路中，可能需要有多个数据结构配合完成此题，而非仅在单个数据结构上进行操作。
允许并鼓励使用 STL 中的相关内容。
