12E. Outside Mex

2500 pts2s256 MB

You are given a permutation $p_1, p_2, \ldots, p_n$ of the numbers $0,1,\ldots,n-1$ .

In one operation, you delete exactly one element from the current array. The deleted element must be either the leftmost element or the rightmost element of the current array.

For each $k$ with $1 \le k \le n$ , define $f(k)$ as follows.

You perform exactly $k$ operations. Let $S$ be the set of values that were deleted. Then $f(k)$ is the maximum possible value of $\operatorname{mex}(S)$ over all valid sequences of operations.

Here, $\operatorname{mex}(S)$ is the smallest non-negative integer that does not belong to $S$ .

Output $f(1), f(2), \ldots, f(n)$ .

Constraints

$1 \le n \le 2 \times 10^5$
$p$ is a permutation of $0,1,\ldots,n-1$

Input

n

p_1 \quad p_2 \quad \cdots \quad p_n

Output

f(1) \quad f(2) \quad \cdots \quad f(n)

Samples

Input

1
0

Explanation

The only deleted value is $0$ . The deleted set is $\{0\}$ , so its mex is $1$ .

Output

Input

5
0 1 2 3 4

Explanation

For every $k$ , delete the first $k$ elements from the left. Then the deleted values are exactly $0,1,\ldots,k-1$ , so the mex is $k$ .

The mex cannot be larger than $k$ , because exactly $k$ values are deleted.

Output

1 2 3 4 5

Input

5
2 0 4 1 3

Explanation

The permutation is $[2,0,4,1,3]$ .

With one deletion, value $0$ cannot be deleted, so the mex is $0$ .

With two or three deletions, value $0$ can be deleted, but values $0$ and $1$ cannot both be deleted. Therefore the best mex is $1$ .

With four deletions, delete two elements from the left and two elements from the right. The deleted values are $\{2,0,1,3\}$ , so the mex is $4$ .

With five deletions, all values are deleted, so the mex is $5$ .

Output

0 1 1 4 5

Input

6
3 0 5 2 1 4

Explanation

The permutation is $[3,0,5,2,1,4]$ .

With one deletion, value $0$ cannot be deleted, so the mex is $0$ .

With two or three deletions, value $0$ can be deleted, but values $0$ and $1$ cannot both be deleted. Therefore the best mex is $1$ .

With four deletions, delete two elements from the left and two elements from the right. The deleted values are $\{3,0,1,4\}$ , so the mex is $2$ .

With five deletions, keep only the third element, whose value is $5$ . The deleted values are $\{3,0,2,1,4\}$ , so the mex is $5$ .

With six deletions, all values are deleted, so the mex is $6$ .

Output

0 1 1 2 5 6

Input

8
4 1 6 0 7 3 2 5

Explanation

The permutation is $[4,1,6,0,7,3,2,5]$ .

For $k=1,2,3$ , value $0$ cannot be deleted, so the mex is $0$ .

For $k=4$ , delete the first four elements. The deleted values are $\{4,1,6,0\}$ , so the mex is $2$ .

For $k=5$ , delete the first four elements and the last element. The deleted values are $\{4,1,6,0,5\}$ , so the mex is still $2$ . Values $0,1,2$ cannot all be deleted using only five deletions.

For $k=6$ , delete the first four elements and the last two elements. The deleted values are $\{4,1,6,0,2,5\}$ , so the mex is $3$ .

For $k=7$ , keep only the fifth element, whose value is $7$ . The deleted values are $\{4,1,6,0,3,2,5\}$ , so the mex is $7$ .

For $k=8$ , all values are deleted, so the mex is $8$ .

Output

0 0 0 2 2 3 7 8

You are given a permutation $p_1, p_2, \ldots, p_n$ of the numbers $0,1,\ldots,n-1$ .

In one operation, you delete exactly one element from the current array. The deleted element must be either the leftmost element or the rightmost element of the current array.

For each $k$ with $1 \le k \le n$ , define $f(k)$ as follows.

You perform exactly $k$ operations. Let $S$ be the set of values that were deleted. Then $f(k)$ is the maximum possible value of $\operatorname{mex}(S)$ over all valid sequences of operations.

Here, $\operatorname{mex}(S)$ is the smallest non-negative integer that does not belong to $S$ .

Output $f(1), f(2), \ldots, f(n)$ .

$1 \le n \le 2 \times 10^5$
$p$ is a permutation of $0,1,\ldots,n-1$

n

p_1 \quad p_2 \quad \cdots \quad p_n

f(1) \quad f(2) \quad \cdots \quad f(n)

The only deleted value is $0$ . The deleted set is $\{0\}$ , so its mex is $1$ .

For every $k$ , delete the first $k$ elements from the left. Then the deleted values are exactly $0,1,\ldots,k-1$ , so the mex is $k$ .

The mex cannot be larger than $k$ , because exactly $k$ values are deleted.

The permutation is $[2,0,4,1,3]$ .

With one deletion, value $0$ cannot be deleted, so the mex is $0$ .

With two or three deletions, value $0$ can be deleted, but values $0$ and $1$ cannot both be deleted. Therefore the best mex is $1$ .

With four deletions, delete two elements from the left and two elements from the right. The deleted values are $\{2,0,1,3\}$ , so the mex is $4$ .

With five deletions, all values are deleted, so the mex is $5$ .

The permutation is $[3,0,5,2,1,4]$ .

With one deletion, value $0$ cannot be deleted, so the mex is $0$ .

With two or three deletions, value $0$ can be deleted, but values $0$ and $1$ cannot both be deleted. Therefore the best mex is $1$ .

With four deletions, delete two elements from the left and two elements from the right. The deleted values are $\{3,0,1,4\}$ , so the mex is $2$ .

With five deletions, keep only the third element, whose value is $5$ . The deleted values are $\{3,0,2,1,4\}$ , so the mex is $5$ .

With six deletions, all values are deleted, so the mex is $6$ .

The permutation is $[4,1,6,0,7,3,2,5]$ .

For $k=1,2,3$ , value $0$ cannot be deleted, so the mex is $0$ .

For $k=4$ , delete the first four elements. The deleted values are $\{4,1,6,0\}$ , so the mex is $2$ .

For $k=5$ , delete the first four elements and the last element. The deleted values are $\{4,1,6,0,5\}$ , so the mex is still $2$ . Values $0,1,2$ cannot all be deleted using only five deletions.

For $k=6$ , delete the first four elements and the last two elements. The deleted values are $\{4,1,6,0,2,5\}$ , so the mex is $3$ .

For $k=7$ , keep only the fifth element, whose value is $7$ . The deleted values are $\{4,1,6,0,3,2,5\}$ , so the mex is $7$ .

For $k=8$ , all values are deleted, so the mex is $8$ .

Outside Mex - Repovive Starter Round 3 | Repovive

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

12E. Outside Mex

Constraints

Input

Output

Samples

12E. Outside Mex

Constraints

Input

Output

Samples