Задача D. Caterpillar ≡

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ a_i, N, L ≤ 10⁶, L ≤ N, a_i ≠ a_i + 1

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

1 4
4 3 2 3

1

3 10
10 9 8 7 8 9 10 9 8 7

4