Ксюша живет в городе, в котором на главной кольцевой дороге находятся n домов. Дома кольцевой пронумерованы от 1 до n по часовой стрелке, по счастливой случайности движение на кольцевой одностороннее и организовано также по часовой стрелке.
Недавно Ксюша переехала на кольцевую в дом с номером 1. В связи с переездом у нее появилось m дел, чтобы сделать i-ое дело, нужно находиться в доме с номером ai, а также сделать все дела с номерами меньше i. Изначально, Ксюша находится в доме с номером 1, найдите какое минимальное количество времени ей нужно потратить, чтобы выполнить все дела, если на переезд между двумя соседними домами на кольцевой требуется одна единица времени.
Выходные данные
Выведите единственное целое число — сколько времени придется потратить Ксюше, чтобы сделать все дела.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом тестовом примере последовательность передвижений Ксюши по кольцевой в оптимальном решении выглядит следующим образом: 1 → 2 → 3 → 4 → 1 → 2 → 3. Итого тратится 6 единиц времени.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
3 2 3
|
6
|
|
2
|
4 3
2 3 3
|
2
|