giúp với mọi người ơi [thuật toán]

[hungngolove]

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) chỉ thị cho máy tráo bài theo cách sau:

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|<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

[nguyenvannam1510]

1. bạn cần hàm
function chuyen(i)
begin
tg = a[i]
for *** := i to 2*n do
begin
a[***] := a[***+1]
a[2*n] := tg
end;
end;

Hàm này để chuyển bài từ vị trí i về cuối

Sau đó hàm tráo bài lên trên (k>0), trường hợp k<0 bạn tự làm nhá
function trao_bai(k)
begin
for i :=1 to 2*k
begin
chuyen(n-i+1)
end;
end;

Cách làm này bạn sẽ rút lá bài ở vị trí n-i+1 chuyển lên đầu số lần là 2*k thay vì chuyển một phát 2*k lá bài. Bạn có thể nghiên cứu cách chuyển 1 phát 2*k lá bài

3. với m phần tử ki, bạn gọi hàm tráo_bài. Vậy là được mảng a sau khi tráo.

4. Giờ là tìm dãy con tăng lớn nhất (không liên tiếp)
Cái này dùng quy hoạch động :D