SHUFFLEK - Shuffling cards

English Vietnamese

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


Added by:sieunhan
Date:2011-06-22
Time limit:0.904s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM Regional Hanoi 2010

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.