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.


-----Input-----

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.


-----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 3
3 2 3

Output
6

Input
4 3
2 3 3

Output
2



-----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.

Difficulty: interview

Starter code:

Solutions:
n, m = list(map(int, input().split()))
v = list(map(int, input().split()))

for i in range(1, len(v)):
    if v[i] < v[i-1]: v[i] += ((v[i-1] - v[i]) // n) * n
    while v[i] < v[i-1]: v[i] += n

print(v[-1]-1)


n, m = map(int, input().split())
a = [1] + list(map(int, input().split()))
time = 0
for i in range(1, m + 1):
    if a[i] >= a[i - 1]:
        time += a[i] - a[i - 1]
    else:
        time += (n - a[i - 1]) + a[i]
print(time)

import sys
n,m=list(map(int,sys.stdin.readline().split()))

Tasks=list(map(int,sys.stdin.readline().split()))

p=1
ans=0
for item in Tasks:
    x=item-p
    if(x<0):
        x=n+x
    ans+=x
    p=item
print(ans)




time=0
house=1
n, m = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

for x in a:
    if x!=house:
        if x>house:
            time+= x-house
        else:
            time+= x + n-house
        house = x

print(time)


n, m = map(int, input().split())
a = list(map(int, input().split()))
s = a[0] - 1
for i in range(1, len(a)):
    if a[i] > a[i-1]:
        s += a[i] - a[i-1]
    elif a[i] < a[i-1]:
        s += n - a[i-1] + a[i]
print(s)

def __starting_point():
    inp = input()
    arr = inp.split()
    n = int(arr[0])
    m = int(arr[1])
    inp = input()
    arr = inp.split()
    L = []
    for a in arr:
        L.append(int(a))
    st = 0
    pr = 1
    ans = 0
    bst = True
    while (st+1)<m:
        if L[st]>L[st+1]:
            if bst:
                ans+=L[st]-pr
                bst=False
            else:
                ans+=L[st]-pr+n
            pr = L[st]
        
        st+=1
    if bst:
        ans+=L[st]-1
    else:
        ans+=L[st]-pr+n
    print(ans)

__starting_point()

n,m = map(int, input().split())
a = [int(x) for x in input().split()]
ans = 0;
a = [1] + a
for i in range(1, len(a)):
    if (a[i] >= a[i - 1]):
        ans += a[i] - a[i - 1]
    else:
        ans += n - a[i - 1] + a[i]
print(ans)

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
i = 0
now = 1
all = 0
while i != m:
    if a[i] - now > 0:
        all += a[i] - now
        now = a[i]
    else:
        if a[i] - now < 0:
            all += (n - now) + a[i]
            now = a[i]
 #   print(all, a[i], now)
    i += 1
print(all)

import sys
f = sys.stdin
#f = open("input.txt", "r")
n, m = map(int, f.readline().strip().split())
p = [int(i) for i in f.readline().strip().split()]
prev = 1
count = 0
for i in p:
    if i > prev:
        count += i-prev
    elif i < prev:
        count += n+i-prev
    prev = i
print(count)

n, m = map(int, input().split())
works = list(map(int, input().split()))
ans = 0
current_home = 1
for i in works:
    ans += n - current_home + 1 + i - 1 if current_home > i else i - current_home
    current_home = i
print(ans)

from sys import stdin

def take():
    n,m=list(map(int,stdin.readline().split()))
    li = list(map(int,stdin.readline().split()))
    count=0
    curr=1
    for val in li:
        if val>=curr:
            count += (val-curr)
        else:
            count += (n-curr) + (val) 
        curr = val
    print(count)
take()


n,m = map(int,input().split())
a = [1] + list(map(int,input().split()))
a1 = []
t = 0
for i in a:
    a1.append(i-1);
for i in range(0,len(a1)-1,1):
    if(a[i+1] >= a[i]):
        t += a[i+1] - a[i]
    else:
        t += n - a[i] + a[i+1]

print(t)

while(1):
    try:
        n,m=list(map(int,input().split()))
        a=list(map(int,input().split()))
        tt=a[0]-1
        for i in range(1,len(a)):
            if a[i]<a[i-1]:
                tt+=n-a[i-1]+a[i]
            else:
                tt+=a[i]-a[i-1]
        print(tt)
    except EOFError:
        break
    
                


n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=1
s=0
for i in range(0,m):
    if b>a[i]:
        s+=a[i]+n-b
    else:
        s+=a[i]-b
    b=a[i]
print(s)

# -*- coding: utf-8 -*-

def solve(n, m, b):
    b = [1] + b
    s = 0
    for i in range(m):
        s += (b[i+1]-b[i] + n) % n
    return s

def test():
    assert solve(4, 3, [3, 2, 3]) == 6
    assert solve(4, 3, [2, 3, 3]) == 2
    print("test passes")

# test()
tmp = input()
n, m = list(map(int, tmp.split()))
tmp = input()
b = list(map(int, tmp.split()))
print(solve(n, m, b))


3

n, m = tuple(map(int, input().split()))
a = [1] + list(map(int, input().split()))
ans = 0
for i, j in zip(a[:-1], a[1:]):
    ans += j - i if j >= i else n - i + j
print(ans)


n,m = map(int, input().split())
a = list(map(int, input().split()))
cnt = a[0] - 1
for i in range(1, m):
    if a[i] == a[i-1]:
        continue
    elif a[i-1] > a[i]:
        cnt += (n - a[i-1]) + a[i]
    else:
        cnt += a[i] - a[i-1]
print(cnt)

n,m = list(map (int, input().split()))
a = list (map (int, input().split()))
ret = 0
cur = 1
for i in a:
  ret += i - cur
  if i < cur:
    ret += n
  cur = i
print (ret)


n, m = map(int, input().split())
a = list(map(int, input().split()))
ans = a[0] - 1
for i in range(1, m):
    if a[i] >= a[i - 1]:
        ans += a[i] - a[i - 1]
    else:
        ans += n - a[i - 1] + a[i]
print(ans)

n, m = map(int, input().split())
a = (1,) + tuple(map(int, input().split()))
ans = 0
for i in range(1, len(a)):
    ans += (a[i] - a[i - 1] + n) % n
print(ans)

n, m = map(int, input().split())
M = list(map(int, input().split()))
now = 1
time = 0
for i in M:
    if i >= now:
        time += i - now
    else:
        time += n - now + i
    now = i
print(time)

n,m=map(int,input().split())
A = list(map(int, input().split()))
k=A[0]-1
for i in range(1,m):
   if A[i]>A[i-1]:
      k+=A[i]-A[i-1]
   if A[i]<A[i-1]:
      k+=n+A[i]-A[i-1]
print(k) 

import sys

n,m = input().split(' ')
dos = input().split(' ')
current = 1
result = 0
circle = list(range(1,int(n)))
for do in dos:
    tmp = int(do) - current
    if tmp < 0:
        result += int(n) + tmp
    else:
        result += tmp
    current = int(do)
print(result)


n, m = [int(x) for x in input().split()]
a = [y for y in reversed([int(x) for x in input().split()])]
t = 0
cur_pos = 1
while len(a) > 0:
    nxt = a.pop()
    if nxt > cur_pos:
        t += nxt-cur_pos
    elif nxt < cur_pos:
        t += n - (cur_pos - nxt)
    cur_pos = nxt

print(t)


n, m = map (int, input().split())
a = list (map (int, input().split())) 


ans = 0
p = 1

for i in a:
  ans += [i - p, i - p + n][i < p]
  p = i
    
print(ans)