O - 最長増加部分列 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

k=1,2,\ldots,N について以下の問題を解いてください。

A_k を任意の実数に置き換えられるとき、置き換えた後の A の最長増加部分列の長さとしてあり得る最大値を求めてください。

最長増加部分列とは

列 A の部分列とは A の要素をいくつか抜き出して元の順に並べてできる列を指します。
列 A の最長増加部分列とは、 A の狭義単調増加な部分列のうち列の長さが最大のものを指します。

制約

  • 1\le N\le 2\times 10^5
  • 1\le A_i\le 10^9
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N

出力

N 行出力せよ。

i 行目には k=i の場合の答えを出力せよ。

入力例 1

3
2 1 3

出力例 1

3
3
2
  • k=1 のとき： 例えば A_1 を 0 に置き換えると、 A=(0,1,3) となります。この場合の最長増加部分列の長さは 3 となります。最長増加部分列の長さを 3 より大きくすることはできないので、 3 が答えです。
  • k=2 のとき： 例えば A_2 を 2.5 に置き換えると、 A=(2,2.5,3) となります。この場合の最長増加部分列の長さは 3 となります。最長増加部分列の長さを 3 より大きくすることはできないので、 3 が答えです。
  • k=3 のとき： 例えば A_3 を 7 に置き換えると、 A=(2,1,7) となります。この場合の最長増加部分列の長さは 2 となります。最長増加部分列の長さを 2 より大きくすることはできないので、 2 が答えです。

入力例 2

4
4 4 4 4

出力例 2

2
2
2
2

入力例 3

10
1 9 1 3 7 9 10 9 7 3

出力例 3

6
6
6
5
5
5
5
6
6
6

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

For each k=1,2,\ldots,N, solve the following problem:

You may replace A_k with an arbitrary real number. Find the maximum possible length of a longest increasing subsequence of A after the replacement.

What is a longest increasing subsequence?

A subsequence of the sequence A is a sequence that can be obtained by extracting some of the elements of A and arranging them in the original order.
A longest increasing subsequence is a strictly monotonically increasing sequence with the maximum length.

Constraints

  • 1\le N\le 2\times 10^5
  • 1\le A_i\le 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print N lines.

In the i-th line, print the answer for k=i.

Sample Input 1

3
2 1 3

Sample Output 1

3
3
2
  • When k=1: for example, replacing A_1 with 0 makes A=(0,1,3), where the length of a longest increasing subsequence is 3. Since the length cannot be made greater than 3, the answer is 3.
  • When k=2: for example, replacing A_2 with 2.5 makes A=(2,2.5,3), where the length of a longest increasing subsequence is 3. Since the length cannot be made greater than 3, the answer is 3.
  • When k=3: for example, replacing A_3 with 7 makes A=(2,1,7), where the length of a longest increasing subsequence is 2. Since the length cannot be made greater than 2, the answer is 2.

Sample Input 2

4
4 4 4 4

Sample Output 2

2
2
2
2

Sample Input 3

10
1 9 1 3 7 9 10 9 7 3

Sample Output 3

6
6
6
5
5
5
5
6
6
6