Problem C. Caterpillar ≡

Statement

A caterpillar of length L crawls over rough terrain. Rough terrain can be represented as a one-dimensional array of N cells with different heights. A cell a_i is called a downhill if a_i > a_i + 1. A cell a_i is called an uphill if a_i < a_i + 1. Initially, the caterpillar occupies the first L cells.

In order to advance one cell, the caterpillar spends 1 second of time. However, if it occupies more downhills than uphills, and the head of the caterpillar is on the downhill, it immediately moves one cell to the right.

Determine after how many seconds the head of the caterpillar reaches the last cell.

Input format

The first line of the input file contains two integers L, N. The second line contains N integers a_i.

Output format

The output must contain one integer — time after which the caterpillar reaches the last cell.

Constraints

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

Sample tests

1 4
4 3 2 3

1

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

4