Truy vấn đoạn phân biệt

Cho một dãy gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$. Bạn cần trả lời $q$ truy vấn; mỗi truy vấn yêu cầu số lượng giá trị khác nhau xuất hiện trong một đoạn con của dãy.

Các truy vấn được mã hóa để buộc phải trả lời trực tuyến (không thể đọc trước toàn bộ). Mỗi truy vấn cho hai số nguyên không âm $x$ và $y$. Gọi $last$ là đáp số của truy vấn ngay trước đó ($last=0$ với truy vấn đầu tiên). Đoạn cần hỏi được tính như sau:

$$l=((x\oplus last)modn)+1,r=((y\oplus last)modn)+1$$

trong đó $\oplus$ là phép XOR. Nếu $l>r$ thì hoán đổi $l$ và $r$. Đáp số của truy vấn là số giá trị khác nhau trong $a_l,a_{l+1},\dots ,a_r$.

Dữ liệu vào

• Dòng 1: số nguyên $n$.
• Dòng 2: $n$ số nguyên $a_1,\dots ,a_n$.
• Dòng 3: số nguyên $q$.
• $q$ dòng tiếp theo, mỗi dòng hai số nguyên $x$ và $y$.

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng chứa số giá trị khác nhau trong đoạn tương ứng.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le q\le 2·{10}^5$
• $1\le a_i\le {10}^9$
• $0\le x,y\le {10}^9$

Ví dụ

Ghi chú

Vì truy vấn buộc trả lời trực tuyến, không thể sắp xếp truy vấn để xử lý ngoại tuyến.