题目描述

提瓦特里有 $n$ 个小岛，第 $i$ 个岛（$1 \le i < n$）和第 $i+1$ 个岛有一座桥连接，第 $1$ 个岛和第 $n$ 个岛有桥连接。
你想按照 $s_1,s_2,s_3,\dots s_m$ 的顺序依次游览 $m$ 座岛。只能通过桥从一个岛到另一个岛。
但现需要断开一座桥。问你任意选择一座桥断开的情况下，完成游览最少要通过多少次桥。
如果一座桥被多次计算，需要重复计算次数。

输入输出格式

输入

共两行

第一行两个整数 $N$ 和 $M$

第二行 $M$ 个整数 X1 到 Xm

输出

一个整数代表答案

样例数据

3 3
1 3 2

2

4 5
2 4 2 4 2

8

数据范围

• $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)$
• 所有的输入都是整数.