Задача D. Caterpillar

Автор:И. Блинов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Гусеница длины L ползёт по пересечённой местности. Пересечённую местность можно представить в виде одномерного массива из N клеток с разными высотами. Клетка ai называется спуском, если ai > ai + 1. Клетка ai называется подъёмом, если ai < ai + 1. Изначально гусеница занимает первые L клеток.

Чтобы продвинуться на одну клетку вперёд, гусеница тратит 1 секунду времени. Однако если среди занимаемых ей клеток спусков больше, чем подъёмов, и голова гусеницы находится на спуске, то она моментально продвигается вправо на одну клетку.

Определите, через сколько секунда голова гусеница достигнет последней клетки.

Формат входных данных

Первая строка входных данных содержит два целых числа L, N. Вторая строка содержит N целых чисел ai.

Формат выходных данных

Выходные данные должны содержать одно целое число — время, через которое гусеница достигнет последней клетки.

Ограничения

1 ≤ ai, N, L ≤ 106, L ≤ N, ai ≠ ai + 1

Примеры тестов

Стандартный вход Стандартный выход
1
1 4
4 3 2 3
1
2
3 10
10 9 8 7 8 9 10 9 8 7
4

0.174s 0.016s 15