Xenia and Ringroad

题面翻译

题意

Xenia住在一个城市里，那里所有的房子都是建在一个环线上的，Xenia现在在1号房子里，她有m个任务要完成，并只能按顺时针方向走（房子排列号码也为顺时针递增）。若她要完成第i个任务，她将要走到第ai个房里。请问她要最少要走多少个单位长度？（若两个任务在一个房子里，则可以不走）。

输入

第一行2个数：第一个为城市里房子的总个数，第二个为有几个任务。

输出

她最少要走的步数。

范围

（2<=房子个数<=100000)

(1<=任务数<=100000）

题目描述

Xenia lives in a city that has $n$ houses built along the main ringroad. The ringroad houses are numbered 1 through $n$ in the clockwise order. The ringroad traffic is one way and also is clockwise.

Xenia has recently moved into the ringroad house number 1. As a result, she's got $m$ things to do. In order to complete the $i$ -th task, she needs to be in the house number $a_{i}$ and complete all tasks with numbers less than $i$ . Initially, Xenia is in the house number 1, find the minimum time she needs to complete all her tasks if moving from a house to a neighboring one along the ringroad takes one unit of time.

输入格式

The first line contains two integers $n$ and $m$ $(2<=n<=10^{5},1<=m<=10^{5})$ . The second line contains $m$ integers $a_{1},a_{2},...,a_{m}$ $(1<=a_{i}<=n)$ . Note that Xenia can have multiple consecutive tasks in one house.

输出格式

Print a single integer — the time Xenia needs to complete all tasks.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

样例 #1

样例输入 #1

4 3
3 2 3

样例输出 #1

6

样例 #2

样例输入 #2

4 3
2 3 3

样例输出 #2

2

提示

In the first test example the sequence of Xenia's moves along the ringroad looks as follows: $1→2→3→4→1→2→3$ . This is optimal sequence. So, she needs 6 time units.