Louder Every Second - Repovive Starter Round 8 | Repovive

23E. Louder Every Second

2500 pts2s256 MB

You are given an array of integers $a_1,a_2,\ldots,a_n$ .

Every second, the following operation is performed simultaneously for all positions $i$ :

Replace $a_i$ with $\max\{a_j \mid \max(1,i-1)\le j\le \min(n,i+1)\}$ .

All replacements use the values from the beginning of that second.

For each position, find how many times its value changes before the array stops changing. The initial assignment of values does not count as a change.

Constraints

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$

Input

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

Output

c_1 \quad c_2 \quad \cdots \quad c_n

Here, $c_i$ is the number of times the value at position $i$ changes before the array stops changing.

Samples

Input

4
3 1 1 2

Explanation

The successive arrays are:

$[3,1,1,2] \to [3,3,2,2] \to [3,3,3,2] \to [3,3,3,3]$ .

The values at positions $1$ , $2$ , $3$ , and $4$ change $0$ , $1$ , $2$ , and $1$ times, respectively. Position $4$ stays unchanged for two seconds before changing to $3$ .

Output

0 1 2 1

Input

5
2 1 2 1 4

Explanation

The successive arrays are:

$[2,1,2,1,4] \to [2,2,2,4,4] \to [2,2,4,4,4] \to [2,4,4,4,4] \to [4,4,4,4,4]$ .

Position $2$ changes from $1$ to $2$ and later to $4$ . Both neighboring occurrences of $2$ reach it in the first second, but that is only one change. Position $5$ never changes, and each remaining position changes once.

Output

1 2 1 1 0

Input

1
1000000000

Explanation

The only element has no neighbors, so its value never changes.

Output

You are given an array of integers $a_1,a_2,\ldots,a_n$ .

Every second, the following operation is performed simultaneously for all positions $i$ :

Replace $a_i$ with $\max\{a_j \mid \max(1,i-1)\le j\le \min(n,i+1)\}$ .

All replacements use the values from the beginning of that second.

For each position, find how many times its value changes before the array stops changing. The initial assignment of values does not count as a change.

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

c_1 \quad c_2 \quad \cdots \quad c_n

Here, $c_i$ is the number of times the value at position $i$ changes before the array stops changing.

The successive arrays are:

$[3,1,1,2] \to [3,3,2,2] \to [3,3,3,2] \to [3,3,3,3]$ .

The values at positions $1$ , $2$ , $3$ , and $4$ change $0$ , $1$ , $2$ , and $1$ times, respectively. Position $4$ stays unchanged for two seconds before changing to $3$ .

The successive arrays are:

$[2,1,2,1,4] \to [2,2,2,4,4] \to [2,2,4,4,4] \to [2,4,4,4,4] \to [4,4,4,4,4]$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

23E. Louder Every Second

Constraints

Input

Output

Samples

23E. Louder Every Second

Constraints

Input

Output

Samples