You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

F. 插队

题目描述

一年一度的猴王争霸赛的报名开始啦！

目前有 $n$ 只猴子排起了长长的队伍，每只猴子都有自己的身高 $h_i$。当然，每只猴子都想排到前面去，于是它们就要插队啦。

每次插队，插队的猴子都会去找目前排在它前面的那只猴子。如果前面那只猴子身高比自己矮，要插队的猴子就会直接用武力解决，从而排到它的前面，即所谓“猴高猴有理”。而对于那些身高比自己高的猴子，就不能直接插队了 T_T。

根据猴国的传统，只要抱在一只猴子的身上并用香蕉贿赂它，就能排到它前面了……然而由于香蕉数量有限，每只猴子最多只能贿赂一只身高比自己高的猴子。

在开始插队之前，每只猴子都想知道，如果只有它一只猴在插队，它最多能排到哪个位置。

输入格式

第一行输入一个正整数 $n$，表示当前排队的猴子的数量。 第二行输入 $n$ 个正整数 $h_i$，表示排在第 $i$ 位置的猴子的身高。

题目保证每只猴子的身高不超过 $10^9$，且每只猴子的身高各不相同。

输出格式

输出 $n$ 行，第 $i$ 行输出一个整数表示只有第 $i$ 只猴子在插队时，它最多能排到哪个位置。

样例

输入

7
7 5 2 6 3 4 1

输出

1
1
2
1
3
3
6

样例解释

• 第一只猴子已经排在队首了，位置为 $1$。
• 第二只猴子贿赂了第一只猴子，也能排在队首，位置为 $1$。
• 第三只猴子贿赂了第二只猴子，排在第二个位置，位置为 $2$。
• 第四只猴子身高比第三只猴子和第二只猴子高，可以直接插队，再贿赂第一只猴子，就可以排在队首，位置为 $1$。
• 第五只猴子和第六只猴子贿赂了第四只猴子，都可以排在身高为5的第二只猴子后面，位置分别为 $3$、$3$。
• 第七只猴子贿赂了第六只猴子，排在第六个位置，位置为 $6$。

数据范围与提示

• 对于 $50\%$ 的测试点，$n \le 5000$。
• 对于 $90\%$ 的测试点，$n \le 200000$。
• 对于 $100\%$ 的测试点，$n \le 1000000$。