B. Ксюша и кольцевая дорога
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ксюша живет в городе, в котором на главной кольцевой дороге находятся n домов. Дома кольцевой пронумерованы от 1 до n по часовой стрелке, по счастливой случайности движение на кольцевой одностороннее и организовано также по часовой стрелке.

Недавно Ксюша переехала на кольцевую в дом с номером 1. В связи с переездом у нее появилось m дел, чтобы сделать i-ое дело, нужно находиться в доме с номером ai, а также сделать все дела с номерами меньше i. Изначально, Ксюша находится в доме с номером 1, найдите какое минимальное количество времени ей нужно потратить, чтобы выполнить все дела, если на переезд между двумя соседними домами на кольцевой требуется одна единица времени.

Входные данные

В первой строке записаны два целых числа n и m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105). В второй строке записаны m целых чисел a1, a2, ..., am (1 ≤ ai ≤ n). Обратите внимание, что Ксюша может иметь несколько дел подряд в одном и том же доме.

Выходные данные

Выведите единственное целое число — сколько времени придется потратить Ксюше, чтобы сделать все дела.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
4 3
3 2 3
Выходные данные
6
Входные данные
4 3
2 3 3
Выходные данные
2
Примечание

В первом тестовом примере последовательность передвижений Ксюши по кольцевой в оптимальном решении выглядит следующим образом: 1 → 2 → 3 → 4 → 1 → 2 → 3. Итого тратится 6 единиц времени.