Xenia 住在一个城市,该城市有 n 栋房屋沿着主环路建造。环路房屋按顺时针顺序编号为 1 至 n。环路交通是单向的,也是顺时针方向的。
Xenia 最近搬进了环路 1 号房子。因此,她有 m 件事要做。为了完成第i个任务,她需要在编号ai的房子里,完成编号小于i的所有任务。最初,Xenia 位于 1 号房屋,如果沿环路从一栋房屋移动到相邻房屋需要一个单位时间,请求出她完成所有任务所需的最短时间。
输入
第一行包含两个整数 n 和 m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105)。第二行包含 m 个整数 a1, a2, ..., am (1 ≤ ai ≤ n)。请注意,Xenia 可以在一栋房子里执行多个连续的任务。
输出
打印单个整数 — Xenia 完成所有任务所需的时间。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
4 3 3 2 3
输出 #1
6
输入 #2
4 3 2 3 3
输出 #2
2
注意
在第一个测试示例中,Xenia 沿环路移动的顺序如下:1 → 2 → 3 → 4 → 1 → 2 → 3。这是最佳顺序。所以,她需要6个时间单位。