题目描述

Xenia 住在一个有 $n$ 个房子的城市，这些房子都建在主环路上。环路上的房子按照顺时针方向从 $1$ 到 $n$ 编号。环路上的交通是单向的，也就是顺时针行驶。

Xenia 最近搬进了环路上的 $1$ 号房子。因此，她有 $m$ 件事情要做。为了完成第 $i$ 项任务，她必须到达编号为 $a_i$ 的房子，并且完成所有编号小于 $i$ 的任务。最开始，Xenia 在 $1$ 号房子。请你计算她完成所有任务所需的最少时间，如果她每走到相邻的下一个房子需要一个时间单位。

输入格式

第一行包含两个整数 $n$ 和 $m$，$2 \le n \le 10^5,\,1 \le m \le 10^5$。
第二行包含 $m$ 个整数 $a_1,a_2,\ldots,a_m$，$1 \le a_i \le n$。注意，Xenia 可能会有多个连续任务在同一个房子。

输出格式

输出一个整数，表示 Xenia 完成所有任务所需的最少时间。

说明/提示

在第一个测试样例中，Xenia 沿环路的移动顺序为：$1 \to 2 \to 3 \to 4 \to 1 \to 2 \to 3$。这是最优方案。因此，她需要 $6$ 个时间单位。

由 ChatGPT 5 翻译

样例

4 3
3 2 3

6

4 3
2 3 3

2