Problem D. Caterpillar ≡

 Author: И. Блинов Time limit: 1 sec Input file: Standard input Memory limit: 256 Mb Output file: Standard output

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 ai is called a downhill if ai > ai + 1. A cell ai is called an uphill if ai < ai + 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 ai.

Output format

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

Constraints

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

Sample tests

No. Standard input Standard output
1
1 4
4 3 2 3
1
2
3 10
10 9 8 7 8 9 10 9 8 7
4

0.146s 0.016s 15