E - Sum of Neighbors

結論を言うと、$N = 2$ のときは答えは $1$ で、それ以外では答えは $2$ です。
実験をしてみましょう。

• $N=2$ のとき、$P = (1, 2)$ とすればよく、集合は $(3)$であり要素数は $1$ です。
• $N=3$ のとき、$P = (1, 3, 2)$ とすればよく、集合は $(4, 5)$であり要素数は $2$ です。
• $N=4$ のとき、$P = (1, 4, 2, 3)$ とすればよく、集合は $(5, 6, 5)$であり要素数は $2$ です。
• $N=5$ のとき、$P = (1, 5, 2, 4, 3)$ とすればよく、集合は $(6, 7, 6, 7)$であり要素数は $2$ です。

このように$P = (1, N, 2, N-1, 3 ...)$ と構築することで、要素数を最小にすることが出来ます。

$N=2$ のときは明らかに答えは $1$ です。以下に $N≧3$ のときについて考えます。
集合の要素を $1$ 種類にできないこと、$2$ 種類には出来ることを示します。
もし、 $1$ 種類にできると仮定すると、同じ要素が $2$ 個以上なければいけない箇所が存在し、$P$ が順列であるということに矛盾します。
また、$2$ 種類にするには$P = (1, N, 2, N-1, 3 ...)$ とすればよいです。これにより、隣同士の和は $N+1$ か $N+2$ のどちらかとなります。