339B.md (1632B)
1 Source: https://codeforces.com/problemset/problem/339/B 2 3 B. Xenia and Ringroad 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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. 22 23 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. 24 25 Input 26 27 The first line contains two integers *n* and *m* (2 ≤ *n* ≤ 105, 1 ≤ *m* ≤ 105). 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. 28 29 Output 30 31 Print a single integer — the time Xenia needs to complete all tasks. 32 33 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. 34 35 Examples 36 37 Input 38 39 ``` 40 4 3 41 3 2 3 42 ``` 43 44 Output 45 46 ``` 47 6 48 ``` 49 50 Input 51 52 ``` 53 4 3 54 2 3 3 55 ``` 56 57 Output 58 59 ``` 60 2 61 ``` 62 63 Note 64 65 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.