本文共 2961 字，大约阅读时间需要 9 分钟。

time limit per test : 2 seconds

memory limit per test : 256 megabytes

input : standard input

output : standard output

Xenia lives in a city that has

$$

n

n

houses built along the main ringroad. The ringroad houses are numbered

$$

1

1

through

$$

n

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

1

. As a result, she’s got m things to do. In order to complete the

$$

i

i

-th task, she needs to be in the house number

$$

a

i

a_i

and complete all tasks with numbers less than

$$

i

i

. Initially, Xenia is in the house number

$$

1

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.

Input

The first line contains two integers

$$

n

n

and

$$

m

m

$$

(

2

 

≤

 

n

 

≤

 

1

0

5

,

 

1

 

≤

 

m

 

≤

 

1

0

5

)

(2 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5)

. The second line contains

$$

m

m

integers

$$

a

1

,

 

a

2

,

 

.

.

.

,

 

a

m

(

1

 

≤

 

a

i

 

≤

 

n

)

a_1, a_2, ..., a_m (1 ≤ a_i ≤ n)

. Note that Xenia can have multiple consecutive tasks in one house.

Output

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.

Examples

input

4 33 2 3output6input4 32 3 3output2

Note

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.

题意

有

$$

n

n

个点围成的圆，每个点编号

$$

1

1

~

$$

n

n

，要求第

$$

i

i

个点的任务必须在

$$

a

i

a_i

点完成，并且必须按照顺序去完成任务。计算完成所有任务需要花费的最小时间（移动一个点花费时间为

$$

1

1

）

嘤嘤嘤，题意读了一年，真的是废了

Code

/*************************************************************************	 > Author: WZY	 > School: HPU	 > Created Time:   2019-03-26 15:36:37	 ************************************************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
           
          
         
        
       
      
     
    
   

转载地址：https://www.cnblogs.com/Friends-A/p/11054962.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！