Chinese Restaurant

题目描述

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.

输入格式

Input is given from Standard Input in the following format: $N$ $p_0$ $\ldots$ $p_{N-1}$

输出格式

Print the answer.

4
1 2 0 3

4

3
0 1 2

3

10
3 9 6 1 7 2 8 0 5 4

5

提示

$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.下面的图显示了一次操作之后的桌面情形。 在这里，有四位满足的人：

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$。

标签: AtCoder|abc268C

来源

AtCoder|abc268C