Bedao Mini Contest 15 - SEQGAME2

View as PDF

Submit solution


Points: 0.55 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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

Notes


Comments

Please read the guidelines before commenting.


There are no comments at the moment.