Baltic Olympiad in Informatics: 2010 Day 2, Problem 1

There is a large number of empty bins in a factory depot. The bins are arranged in a single row. The manager of the depot wants to put some bins into other bins to make some free space in the left end of the depot. Bins can be moved by a robot, which can take a bin, carry it to the right, and put it into a strictly larger bin. This three-operation sequence is the only allowed way to move bins.

Because of safety regulations, any bin can contain at most one other bin, which must be empty. The manager also wants to keep the double bins in the left end of the resulting row, to make it easier to keep track of them.

You are to write a program that computes the largest possible ~K~ such that the ~2K~ leftmost bins can become ~K~ double bins using the robot's operations.

Constraints

~2 \le N \le 2 \times 10^4~

~1 \le M \le 10^3~

Input Specification

The first line of input contains two space-separated integers: ~M~, the size of the largest bin, and ~N~, the number of bins. The second line contains ~N~ space-separated integers ~A_i~ ~(1 \le A_i \le M)~: the sizes of the bins, listed from left to right.

Output Specification

Output a single integer, the largest number ~K~ such that the robot can turn the ~2K~ leftmost bins into ~K~ double bins. These ~K~ double bins must be the ~K~ leftmost bins (or the prefix) of the resulting row.

Sample Input

5 10
2 2 1 4 3 2 5 4 2 3

Sample Output

4

Explanation

The bins ~[2, 2, 1, 4]~ can be placed in the bins ~[3, 2, 5, 4]~. The double bins are the prefix of the row after the operations.