#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Outside Mex - Repovive Starter Round 3 | Repovive

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$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

12E. Outside Mex

Constraints

Input

Output

Samples

12E. Outside Mex

Constraints

Input

Output

Samples