Increasing Sequence

Time limit3sMemory limit1024 MB

Summary

Given a permutation, for each index i, count the indices j other than i whose removal shortens the longest increasing subsequence that contains i.

Level: Hard8 of 10
Topics: Dynamic programming, Binary search, Segment tree
Solved: No attempts yet

Problem

You are given a permutation of size $N$ . For each $i$ , count the indices $j \neq i$ such that removing $j$ decreases the maximum possible length of an increasing subsequence that contains index $i$ .

Input

The first line contains an integer $N$ .

The next line contains $N$ integers $A_1, A_2, \cdots, A_N$ .

Output

Print $N$ integers, separated by spaces, where the $i$ -th integer is the answer for index $i$ .

Constraints

$1 \leq N \leq 250\,000$
$1 \leq A_i \leq N$
Every $A_i$ is distinct.

Examples5

Example 1
Input
```
1
1
```
Expected output
```
0
```
Example 2
Input
```
6
1 2 3 4 5 6
```
Expected output
```
5 5 5 5 5 5
```
Example 3
Input
```
6
6 5 4 3 2 1
```
Expected output
```
0 0 0 0 0 0
```
Example 4
Input
```
4
2 1 4 3
```
Expected output
```
0 0 0 0
```
Example 5
Input
```
9
1 2 3 6 5 4 7 8 9
```
Expected output
```
5 5 5 6 6 6 5 5 5
```