AT_abc338_d [ABC338D] Island Tour

[problemUrl]: https://atcoder.jp/contests/abc338/tasks/abc338_d AtCoder 諸島は $ N $ 個の島からなり、これらの島々は $ N $ 本の橋によって結ばれています。 島には $ 1 $ から $ N $ までの番号が付けられていて、$ i\ (1\leq\ i\leq\ N-1) $ 本目の橋は島 $ i $ と島 $ i+1 $ を、$ N $ 本目の橋は島 $ N $ と島 $ 1 $ を双方向に結んでいます。 橋を渡る以外に島の間を行き来する方法は存在しません。 AtCoder 諸島では、島 $ X_1 $ から始めて島 $ X_2,X_3,\dots,X_M $ を順に訪れる**ツアー**が定期的に催行されています。 移動の過程で訪れる島とは別の島を経由することもあり、ツアー中に橋を通る回数の合計がツアーの**長さ**と定義されます。 厳密には、**ツアー**とは以下の条件を全て満たす $ l+1 $ 個の島の列 $ a_0,a_1,\dots,a_l $ のことであり、その**長さ** は $ l $ として定義されます。 - 全ての $ j\ (0\leq\ j\leq\ l-1) $ について、島 $ a_j $ と島 $ a_{j+1} $ は橋で直接結ばれている - ある $ 0\ ＝\ y_1\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ X_1 $ $ X_2 $ $ \dots $ $ X_M $

答えを整数として出力せよ。

### 制約 - $ 3\leq\ N\ \leq\ 2\times\ 10^5 $ - $ 2\leq\ M\ \leq\ 2\times\ 10^5 $ - $ 1\leq\ X_k\leq\ N $ - $ X_k\neq\ X_{k+1}\ (1\leq\ k\leq\ M-1) $ - 入力は全て整数 ### Sample Explanation 1 \- $ 1 $ 本目の橋を封鎖した場合：通る島の列として $ (a_0,a_1,a_2)=(1,3,2) $ を取ることで島 $ 1,3,2 $ を順に訪れることができ、長さ $ 2 $ のツアーが催行できます。これより短いツアーは存在しません。 - $ 2 $ 本目の橋を封鎖した場合：通る島の列として $ (a_0,a_1,a_2,a_3)=(1,3,1,2) $ を取ることで島 $ 1,3,2 $ を順に訪れることができ、長さ $ 3 $ のツアーが催行できます。これより短いツアーは存在しません。 - $ 3 $ 本目の橋を封鎖した場合：通る島の列として $ (a_0,a_1,a_2,a_3)=(1,2,3,2) $ を取ることで島 $ 1,3,2 $ を順に訪れることができ、長さ $ 3 $ のツアーが催行できます。これより短いツアーは存在しません。 よって、封鎖する橋をうまく選んだときのツアーの長さの最小値は $ 2 $ です。 以下の図は左から順に橋 $ 1,2,3 $ を封鎖した場合を表し、数字の書かれた丸が島、丸同士を結ぶ線が橋、青い矢印が最短のツアーの経路を表します。 !\[\](https://img.atcoder.jp/abc338/ad4a27665d9da939ab495acd3d05181a.png) ### Sample Explanation 2 $ X_1,X_2,\dots,X_M $ の中に同じ島が複数回現れることもあります。