Giải bài trực tuyến

A deck of 2N cards with distinct values of 1,2, …, 2N is given to the shuffling machine. At the beginning, the cards are arranged in the deck in ascending order from the top to the bottom. The shuffling machine executes a sequence of M instructions determined by M integers k1, k2,…, kM for shuffling the cards. The instruction determined by the number ki (1 ≤ |ki| < N), commands the machine to shuffle the cards as follows:

• If ki > 0: remove a pile of 2ki cards at the middle of the deck and stacks them on top of the deck.
• If ki < 0: remove a pile of -2ki cards at the middle of the deck and inserts them into bottom of the deck.

Mr. X received the deck after it has been shuffled according to M instructions. He wants to throw away some cards from the deck in such a way that the values of the remained cards are in an increasing order from the top to the bottom. Given the M instructions for the shuffling machine, your task is to write a program to help Mr. X determine the minimum number of cards to be removed after the deck has been shuffled.

Input
The first line contains two positive integers N and M (2 ≤ N ≤ 10^9; 0 ≤ M ≤ 10^5) separated by a space. The second line contains M integer k1, k2,…, kM separated by a space.

Output
The minimum number of cards to be removed after the deck has been shuffled.

Sample Input

3 2

-2 1

Sample Output

2