Cho dãy \(a_1,a_2,\ldots,a_n\) đã được sắp xếp không giảm. Với mỗi truy vấn \([l,r]\), hãy tìm số lần xuất hiện nhiều nhất của một giá trị trong đoạn đó.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Mỗi bộ test có dạng:

• Dòng đầu chứa \(n\) và \(q\).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1,\ldots,a_n\).
• \(q\) dòng sau, mỗi dòng chứa hai chỉ số \(l,r\).

Một dòng chỉ chứa số 0 kết thúc dữ liệu; dòng này không thuộc bộ test nào.

Dữ liệu ra

Với mỗi truy vấn, in số lần xuất hiện nhiều nhất trên một dòng. In lần lượt theo thứ tự bộ test và truy vấn.

Ràng buộc

• \(1\le n,q\le100\,000\) trong mỗi bộ test.
• \(-100\,000\le a_i\le100\,000\).
• \(a_i\le a_{i+1}\) với \(1\le i<n\).
• \(1\le l\le r\le n\).

Ví dụ

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

1
4
3

Nguồn

UVa 11235 — Frequent values, cũng có trên SPOJ FREQUENT.