G. Increasing Sequence
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a permutation of size $$$N$$$. For each $$$i$$$, print the number of indices $$$j \neq i$$$, which when removed, decreases the maximum possible length of an increasing subsequence that contains index $$$i$$$.

Input

The first line contains an integer $$$N$$$. ($$$1 \le N \le 250000$$$).

The next line contains $$$N$$$ integers $$$A_1, A_2, \cdots, A_N$$$ denoting the permutation. ($$$1 \le A_i \le N$$$, all $$$A_i$$$s are distinct).

Output

Print $$$N$$$ integers, separated by spaces, denoting the answers for $$$i = 1, 2, 3, \cdots, N$$$.

Examples
Input
1
1
Output
0
Input
6
1 2 3 4 5 6
Output
5 5 5 5 5 5
Input
6
6 5 4 3 2 1
Output
0 0 0 0 0 0
Input
4
2 1 4 3
Output
0 0 0 0
Input
9
1 2 3 6 5 4 7 8 9
Output
5 5 5 6 6 6 5 5 5