Problem C2. 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.106s 0.022s 15