Codeforces Round 197 (Div. 2) |
---|
Закончено |
Ксюша живет в городе, в котором на главной кольцевой дороге находятся 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 единиц времени.
Название |
---|