Giá trị xuất hiện nhiều nhất (Frequent Values)

Nguồn: UVa

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

Cho dãy $A_1,A_2,\ldots,A_N$ đã được sắp theo thứ tự không giảm. Có $Q$ truy vấn, mỗi truy vấn cho hai chỉ số $i,j$ với $1\le i\le j\le N$.

Với mỗi truy vấn, hãy xác định số lần xuất hiện lớn nhất của một giá trị bất kỳ trong đoạn $A_i,A_{i+1},\ldots,A_j$.

Phiên bản gốc UVa chứa nhiều test case và kết thúc bằng dòng 0. Phiên bản này chỉ chứa một test case để phù hợp cơ chế chấm của Phước Hưng OJ.

Input

Dòng đầu chứa hai số nguyên $N,Q$.

Dòng thứ hai chứa $N$ số nguyên $A_1,\ldots,A_N$ và luôn thỏa $A_i\le A_{i+1}$.

$Q$ dòng tiếp theo, mỗi dòng chứa $i,j$.

Output

Với mỗi truy vấn, in số lần xuất hiện của giá trị xuất hiện nhiều nhất trong đoạn $[i,j]$.

Subtask

• Subtask 1 — 20%: $1\le N,Q\le 50$, $-1000\le A_i\le 1000$.
• Subtask 2 — 30%: $1\le N,Q\le 5000$, $-10^5\le A_i\le 10^5$.
• Subtask 3 — 50%: $1\le N,Q\le 10^5$, $-10^5\le A_i\le 10^5$.

Ví dụ

Input

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

Output

1
4
3

Giải thích

Ở truy vấn $[1,10]$, giá trị $1$ xuất hiện $4$ lần nên tần suất lớn nhất là $4$.