Sau trận thua của Argentina trước Saudi Arabia bao nhiêu tài sản của Tri_phan đã bị cuốn theo chiều gió .Thấy Tri_phan khóc lóc thảm thương thần chó Mbfibat đã hiện lên và cho Tri_phan một cơ hội làm lại cuộc đời. Cụ thể thần giao cho một bài toán và bắt anh phải làm, chỉ cần giải xong là Tri_phan đã có thể có đủ tiền về bờ nhưng khổ là anh lại đang vùi đầu trong đống deadline T^T . Bạn hãy giúp Tri_phan giải bài toán trên nhé.
Bài toán như sau :
Bạn có một dãy ~a~ gồm ~N~ phần tử .
Có hai thao tác được biến đổi được sử dụng vô số lần:
+ Bạn chọn ~1~ vị trí ~i~ bất kỳ sao cho ~(1 \le i \le N)~ , bạn được đổi giá trị ~a[i]~ thành giá trị bất kỳ.
+ Dịch phải toàn bộ dãy ~a~ từ dãy ~a[1] , a[2] , ... , a[N]~ thành ~a[N] , a[1] , a[2] , ... , a[N - 1]~.
Có ~q~ truy vấn mỗi truy vấn có dạng ~x , b~ ~(1 \le x \le N , 1 \le b \le 10^{9})~ , bạn cần đổi giá trị ~a[x] = b~ và đếm số thao tác tối thiểu để đưa dãy về dãy có dạng ~1 , 2 , 3, ... , N~ (lưu ý giá trị ~a[x]~ thay đổi theo từng truy vấn).
Input
Dòng đầu tiên chứa số nguyên dương ~N~ ~(1\le N \le 10^{5})~.
Dòng thứ hai chứa ~N~ số nguyên ~a[i]~ cách nhau bởi dấu cách ~(1 \le i \le N , 1 \le a[i] \le 10^{9})~.
Dòng thứ ba chứa ~q~ là số truy vấn ~(1\le q \le 10^{5})~.
q dòng tiếp theo mỗi dòng chứa hai số nguyên dương cách nhau bởi dấu cách là ~x~ và ~b~ ~(1 \le x \le N , 1 \le b \le 10^{9})~
Output
- Với mỗi truy vấn ta in ra số thao tác tối thiểu nằm trên từng dòng một.
Subtask
~20\%~ số test có ~N\le 100, 1\le q \le 1000~.
~30\%~ số test có ~N\le 5000, 1\le q \le 5000~.
~50\%~ số test còn lại không có điều kiện gì thêm.
Sample Input 1
4
1 2 3 5
5
4 4
4 1
3 4
2 3
1 2
Sample Output 1
0
1
2
2
1
Bình luận