/ 
Time Limit: 2 sec / Memory Limit: 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 m は a-x が m の倍数となるような 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