---
# System prepended metadata

title: Trò chơi trên dãy số

---

# Trò chơi trên dãy số 

Bạn có một dãy $a$ gồm $n$ $(1 \leq n \leq 10^5)$ phần tử $a_1, a_2, ..., a_n$. $(1 \leq a_i \leq 10^9)$. 

Có hai thao tác có biến đổi được sử dụng vô số lần:

* Chọn một vị trí $i$ bất kì $(1 \leq a_i \leq n)$, đổi giá trị của $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 dãy $a_n, a_1, ..., a_{n-1}$.

Có $q$ $(1 \leq q \leq 10^5)$ truy vấn, mỗi truy vấn có dạng $x$, $b$ $(1 \leq x \leq n, 1 \leq b \leq 10^9)$, bạn cần đổi giá trị $a_x = b$. Tính số thao tác tối thiểu để đưa dãy $a$ về dạng $1, 2, 3, ..., n$.

Subtask $1$ ($20$ điểm): $n \leq 100, q \leq 1000$.

Subtask $2$ ($30$ điểm): $n \leq 5000, q \leq 5000$.

Subtask $3$ ($50$ điểm): không có ràng buộc gì thêm.


