SHUFFLEK - Shuffling cards

English Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/shufflek


Một bộ bài gồm 2n quân bài được đưa vào máy tráo bài, trên các lá bài từ trên xuống dưới, người tag hi lần lượt các số từ 1 tới 2n. Máy tráo bài thực hiện một dãy m lệnh biểu diễn bởi m số nguyên k1,k2,…,km, mỗi lệnh ki (1<=|ki|

  • Nếu ki>0: Máy lấy 2ki lá bài ở chính giữa bộ bài và đặt chúng lên trên cùng của bộ bài.
  • Nếu ki<0: Máy lấy -2ki lá bài ở chính giữa bộ bài và chèn chúng xuống dưới cùng bộ bài.

Giáo sư X nhận lại bộ bài sau khi đã được tráo bởi m lệnh k1,k2,…,km. Ông ta muốn rút bỏ vài lá bài ở trong bộ bài sao cho các số ghi trên các quân bài từ trên xuống dưới có thứ tự tăng dần.

Nhiệm vụ của bạn là hãy giúp giáo sư X xác định số lượng ít nhất các lá bài phải trút bỏ.

Input

Dòng 1 chứa 2 số nguyên dương n,m (2<=n<=10^9; m<=10^5),

Dòng 2 chứa m số nguyên dương k1,k2,…,km (1<=|ki|

Các số trên một dòng được ghi cách nhau bởi một dấu cách.

Output

Một số nguyên là số lượng ít nhất các lá bài phải rút bỏ

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.