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 ai 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 ≤ 105, 1 ≤ m ≤ 105). The second line contains m integers a1, a2, ..., am (1 ≤ ai ≤ 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.
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
<問題文 意訳>
Xenia たんは n 戸の家が並ぶ環状道路がある街に住んでいます．
その環状道路の家には，時計回りに1番からn番までの番号が振られています．
また，その環状道路は一方通行で時計回りになっています．

Xenia たんは1番の家へ行ったら，m 個の用事を任されてしまいました．
i 番目の用事を終わらせるためには，ai 番の家にいなければなりません．
はじめは，Xeniaたんは1番の家にいるものとして，全ての用事を済ませるために必要な最小時間を求めてください．
もし，a 番の家から，その隣の家に移動する場合，1単位時間の移動時間がかかります．

入力
1行目には，2つの整数 n と m が入力される．n は家の数，m は，用事の数を示す．
2行目には，m 個の整数 a1 ... am が入力される．ai はその仕事をする際にいなければならない家を示す．
ただし，Xeniaたんは1つの家で複数の用事を同時に終わらせることができる点は意識して下さい．

出力
全ての用事をこなすためにかかる時間を1つの整数で出力する．
"""

## プロトタイプ
def xenia_and_ringroad():

    # 入力
    nr_houses, nr_tasks = map(int, raw_input().split(' '))
    next_houses = map(int, raw_input().split(' '))

    # 計算
    # 1. 次の目的地までの移動時間は (a[i] - a[i-1] + (n + 1)) % (n + 1)
    #    a[i] を 0-origin にすると剰余が楽なので先に全要素を -1 する
    next_houses = map((lambda x: x-1), next_houses)

    # 2. 全要素に対して現在位置を進めつつ時間を加算する
    time = 0
    cur_house = 0
    for next_house in next_houses:
        time += ( next_house - cur_house + nr_houses ) % nr_houses
        cur_house = next_house

    # 出力
    print time

if __name__ == '__main__':
    xenia_and_ringroad()
