codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.