Xây dựng quân đội (Army Creation)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ chiến binh, chiến binh $i$ có loại $a_i$. Một quân đội cân bằng được chọn từ một đoạn chỉ số và chứa không quá $k$ chiến binh của mỗi loại. Mỗi kế hoạch được mã hóa bởi $x,y$ và phụ thuộc đáp án trước last, ban đầu $0$: l=((x+last)mod n)+1, r=((y+last)mod n)+1, rồi đổi chỗ nếu $l>r$. Hãy in kích thước lớn nhất của một quân đội cân bằng chọn từ $[l,r]$.

Dữ liệu vào

Dòng đầu chứa $n,k$. Dòng thứ hai chứa các loại $a_i$. Dòng thứ ba chứa $q$. Mỗi trong $q$ dòng sau chứa $x,y$.

Kết quả

In đáp án của từng kế hoạch; đáp án đó trở thành last cho kế hoạch kế tiếp.

Subtask

Subtask 1 (20%)

• $n\le 30$, số truy vấn $\le 30$.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, số truy vấn $\le 3000$.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n,k\le10^5$
• $1\le a_i\le10^5$
• $1\le q\le10^5$
• $1\le x,y\le n$

Ví dụ

Input

6 2
1 1 1 2 2 2
5
1 6
4 3
1 1
2 6
2 6

Output

2
4
1
3
2

Giải thích

Với $k=2$, trong bất kỳ đoạn nào ta có thể lấy tối đa hai chiến binh của mỗi loại. Các khoảng thật được giải mã tuần tự bằng last, nên không thể đổi thứ tự truy vấn.