Shuffling cards

View as PDF

Submit solution

Points: 1.60 (partial)
Time limit: 1.7s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
ACM Regional Hanoi 2010
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một bộ bài gồm ~2 \times n~ 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 ta ghi lần lượt các số từ ~1~ tới ~2 \times n~. 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 ~k_1~, ~k_2~, ..., ~k_m~, mỗi lệnh ~k_i~ ~(1 \le |k_i| < n)~ chỉ thị cho máy tráo bài theo cách sau:

  • Nếu ~k_i > 0~: Máy lấy ~2k_i~ 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 ~k_i < 0~: Máy lấy ~-2k_i~ 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 ~k_1~, ~k_2~, ..., 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ỏ.

image

Input

Dòng ~1~ chứa ~2~ số nguyên dương ~n~, ~m~ ~(2 \le n \le 10^{9}~; ~m \le 10^{5})~,

Dòng ~2~ chứa ~m~ số nguyên dương ~k_1~, ~k_2~, ..., ~k_m~ ~(1 \le |k_i| < n)~.

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.