E - Hiking Course on a Mountain Trail Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は山岳地帯のハイキングコースの整備を担当しています。このコースには N 個のチェックポイントが一列に並んでおり、左から i 番目のチェックポイントの現在の標高は H_i です。

安全管理のため、青木君はコースの整備について次の条件を要求しています：

  • すべてのチェックポイントの標高は非負整数であること。
  • 隣り合うどの 2 つのチェックポイントについても、標高の差の絶対値がちょうど 1 であること。つまり、整備後の i 番目のチェックポイントの標高を H'_i としたとき、すべての 1 \le i \le N - 1 について |H'_i - H'_{i+1}| = 1 を満たすこと。

高橋君は、上の条件を満たすように各チェックポイントの標高を非負整数の範囲で自由に設定し直すことができます。ただし、チェックポイントの標高を変更するには大がかりな工事が必要なため、できるだけ現在の標高のまま残せるチェックポイントの数を多くしたいと考えています。

すなわち、上の条件を満たす非負整数列 H'_1, H'_2, \ldots, H'_N を適切に定めたとき、H_i = H'_i となるチェックポイントの個数の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq H_i \leq 10^9
  • 入力はすべて整数である。

入力

N
H_1 H_2 \ldots H_N
  • 1 行目には、チェックポイントの個数を表す整数 N が与えられる。
  • 2 行目には、各チェックポイントの現在の標高を表す N 個の整数 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。

出力

現在の標高のまま残せるチェックポイントの個数の最大値を 1 行で出力せよ。

入力例 1

5
0 1 2 1 0

出力例 1

5

入力例 2

6
2 2 2 2 2 2

出力例 2

3

入力例 3

15
2 3 4 5 4 3 2 100 99 98 97 0 1 1000000000 999999999

出力例 3

7

入力例 4

50
0 1 0 1 2 3 10 9 8 20 19 18 17 16 15 14 13 12 11 10 0 0 0 5 4 3 2 1 0 1 2 100 101 102 103 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36

出力例 4

15

入力例 5

1
1000000000

出力例 5

1

Score : 433 pts

Problem Statement

Takahashi is in charge of maintaining a hiking course in a mountainous area. This course consists of N checkpoints lined up in a row, and the current elevation of the i-th checkpoint from the left is H_i.

For safety management, Aoki requires the following conditions for the maintenance of the course:

  • The elevation of every checkpoint must be a non-negative integer.
  • For any two adjacent checkpoints, the absolute difference in their elevations must be exactly 1. That is, if we denote the elevation of the i-th checkpoint after maintenance as H'_i, then |H'_i - H'_{i+1}| = 1 must hold for all 1 \le i \le N - 1.

Takahashi can freely reassign the elevation of each checkpoint to non-negative integers so that the conditions above are satisfied. However, since changing the elevation of a checkpoint requires large-scale construction, he wants to keep as many checkpoints at their current elevations as possible.

In other words, when we appropriately determine a sequence of non-negative integers H'_1, H'_2, \ldots, H'_N that satisfies the conditions above, find the maximum number of checkpoints for which H_i = H'_i.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq H_i \leq 10^9
  • All input values are integers.

Input

N
H_1 H_2 \ldots H_N
  • The first line contains an integer N, representing the number of checkpoints.
  • The second line contains N space-separated integers H_1, H_2, \ldots, H_N, representing the current elevations of the checkpoints.

Output

Print the maximum number of checkpoints that can be kept at their current elevations in a single line.

Sample Input 1

5
0 1 2 1 0

Sample Output 1

5

Sample Input 2

6
2 2 2 2 2 2

Sample Output 2

3

Sample Input 3

15
2 3 4 5 4 3 2 100 99 98 97 0 1 1000000000 999999999

Sample Output 3

7

Sample Input 4

50
0 1 0 1 2 3 10 9 8 20 19 18 17 16 15 14 13 12 11 10 0 0 0 5 4 3 2 1 0 1 2 100 101 102 103 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36

Sample Output 4

15

Sample Input 5

1
1000000000

Sample Output 5

1