102682: [AtCoder]ABC268 C - Chinese Restaurant
Description
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
Input
题意翻译
#### 题意 有 $N$ 个人从 $0$ 开始编号， 按逆时针顺序间隔均匀地坐在转盘周围。 在开始时， 第 $p_{i}$ 盘菜在第 $i$ 个人的前面。 现在， 你可以进行以下操作 $0$ 次或多次。 - 将转盘逆时针旋转 $\frac{1}{N}$ 圈。也就是说， 旋转前在第 $i$ 号人面前的盘子现在在 $(i+1)\bmod N$ 号人面前了。 当你结束操作后，如果第 $i$ 盘菜在第 $(i-1)\bmod N$ 个人、第 $i$ 个人或第 $(i+1)\bmod N$ 个人面前，第 $i$ 个人就会感到高兴。 请求出你最多能使多少人感到高兴。 #### 数据范围 - $3 \leq N \leq 2 × 10^{5} $ - $0 \leq p_{i} \leq N - 1$ - 当 $i \ne j$ 时 $p_{i}\ne p_{j}$ - 所有输入都是整数 --- #### 输入格式 使用标准输入以以下格式读入： ``` N p0 ... pN-1 ``` #### 输出格式 直接输出答案 --- #### 样例解释1 下图是一次操作后的桌面  这里有四个人感到快乐： - 第 $0$ 个人感到快乐，因为第 $0$ 盘菜在第 $3\ (=(0 - 1) \bmod 4)$ 个人面前； - 第 $1$ 个人感到快乐，因为第 $1$ 盘菜在第 $1$ 个人面前 - 第 $2$ 个人感到快乐，因为第 $2$ 盘菜在第 $2$ 个人面前 - 第 $3$ 个人感到快乐，因为第 $3$ 盘菜在第 $0\ (=(3+1)\bmod 4)$ 个人面前 很显然不能有五个或更多的人感到快乐了，所以答案是 $4$ .Output
问题描述
Person $0$，Person $1$，$\ldots$，和Person $(N-1)$按逆时针方向均匀地坐在一张转盘周围。Dish $p_i$在桌子前面对着Person $i$。
你可以执行0次或多次以下操作：
- 逆时针转动转盘$N$分之一圈。结果，旋转前在Person $i$前面的盘子现在在Person $(i+1) \bmod N$前面。
当你完成后，如果Dish $i$在Person $(i-1) \bmod N$，Person $i$或Person $(i+1) \bmod N$前面，Person $i$就会感到幸福。
找到可能的最大幸福人数。
什么是$a \bmod m$？
对于整数$a$和正整数$m$，$a \bmod m$表示在$0$到$(m-1)$（包括）之间的整数$x$，使得$(a-x)$是$m$的倍数。 （可以证明这样的$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
下图显示了旋转一次后的桌子。
这里有四个人感到幸福：
- Person $0$感到幸福，因为Dish $0$在Person $3\ (=(0-1) \bmod 4)$前面；
- Person $1$感到幸福，因为Dish $1$在Person $1\ (=1)$前面；
- Person $2$感到幸福，因为Dish $2$在Person $2\ (=2)$前面；
- Person $3$感到幸福，因为Dish $3$在Person $0\ (=(3+1) \bmod 4)$前面。
不可能有五个或更多人感到幸福，所以答案是$4$。
样例输入2
3 0 1 2
样例输出2
3
样例输入3
10 3 9 6 1 7 2 8 0 5 4
样例输出3
5