← 返回题目列表

Codeforces · 339/B

B. Xenia 和 Ringroad

中文机器翻译题面 查看原题

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个时间单位。