C - Chinese Restaurant 解説 /

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

配点 : 300

問題文

回転テーブルの周りに人 0、人 1\ldots、人 N-1 がこの順番で反時計回りに等間隔で並んでいます。また、人 i の目の前には料理 p_i が置かれています。
あなたは次の操作を 0 回以上何度でも行うことが出来ます。

  • 回転テーブルを反時計回りに 1 周の \frac{1}{N} だけ回す。これによって、(この操作の直前に)人 i の目の前にあった料理は人 (i+1) \bmod N の目の前に移動する。

操作を完了させた後において、人 i は料理 i が人 (i-1) \bmod N、人 i、人 (i+1) \bmod N のいずれかの目の前に置かれていると喜びます。
喜ぶ人数の最大値を求めてください。

a \bmod m とは 整数 a と正整数 m に対し、a \bmod ma-xm の倍数となるような 0 以上 m 未満の整数 x を表します。(このような x は一意に定まることが証明できます)

制約

  • 3 \leq N \leq 2 \times 10^5
  • 0 \leq p_i \leq N-1
  • i \neq j ならば p_i \neq p_j
  • 入力はすべて整数

入力

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

N
p_0 \ldots p_{N-1}

出力

答えを出力せよ。


入力例 1

4
1 2 0 3

出力例 1

4

操作を 1 回行うと下の画像のようになります。

この時、4 人が喜ぶことを以下のように確かめられます。

  • 0 は料理 0 が人 3\ (=(0-1) \bmod 4) の目の前に置かれているので喜びます。
  • 1 は料理 1 が人 1\ (=1) の目の前に置かれているので喜びます。
  • 2 は料理 2 が人 2\ (=2) の目の前に置かれているので喜びます。
  • 3 は料理 3 が人 0\ (=(3+1) \bmod 4) の目の前に置かれているので喜びます。

5 人以上が喜ぶことは無いため、答えは 4 です。


入力例 2

3
0 1 2

出力例 2

3

入力例 3

10
3 9 6 1 7 2 8 0 5 4

出力例 3

5

Score : 300 points

Problem Statement

Person 0, Person 1, \ldots, and Person (N-1) are sitting around a turntable in their counterclockwise order, evenly spaced. Dish p_i is in front of Person i on the table.
You may perform the following operation 0 or more times:

  • Rotate the turntable by one N-th of a counterclockwise turn. As a result, the dish that was in front of Person i right before the rotation is now in front of Person (i+1) \bmod N.

When you are finished, Person i is happy if Dish i is in front of Person (i-1) \bmod N, Person i, or Person (i+1) \bmod N.
Find the maximum possible number of happy people.

What is a \bmod m? For an integer a and a positive integer m, a \bmod m denotes the integer x between 0 and (m-1) (inclusive) such that (a-x) is a multiple of m. (It can be proved that such x is unique.)

Constraints

  • 3 \leq N \leq 2 \times 10^5
  • 0 \leq p_i \leq N-1
  • p_i \neq p_j if i \neq j.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
p_0 \ldots p_{N-1}

Output

Print the answer.


Sample Input 1

4
1 2 0 3

Sample Output 1

4

The figure below shows the table after one operation.

Here, there are four happy people:

  • Person 0 is happy because Dish 0 is in front of Person 3\ (=(0-1) \bmod 4);
  • Person 1 is happy because Dish 1 is in front of Person 1\ (=1);
  • Person 2 is happy because Dish 2 is in front of Person 2\ (=2);
  • Person 3 is happy because Dish 3 is in front of Person 0\ (=(3+1) \bmod 4).

There cannot be five or more happy people, so the answer is 4.


Sample Input 2

3
0 1 2

Sample Output 2

3

Sample Input 3

10
3 9 6 1 7 2 8 0 5 4

Sample Output 3

5