Khoảng Cách Lặp Lại Xa Nhất

Cho dãy số nguyên $a_1,a_2,\dots ,a_n$. Với đoạn $[l,r]$, xét mọi cặp chỉ số $i<j$ thỏa $l\le i<j\le r$ và $a_i=a_j$. Khoảng cách của cặp là $j-i$. Hãy tìm khoảng cách lớn nhất. Nếu không có hai vị trí nào trong đoạn mang cùng giá trị, đáp án là $0$.

Input

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• Dòng thứ ba chứa số nguyên $q$.
• Mỗi trong $q$ dòng tiếp theo chứa hai số nguyên $l$ và $r$.

Output

• Với mỗi truy vấn, in trên một dòng khoảng cách lớn nhất; in $0$ nếu mọi giá trị trong đoạn đều khác nhau.

Constraints

• $1\le n,q\le 2\cdot 10^5$.
• $1\le a_i\le 2\cdot 10^9$.
• $1\le l\le r\le n$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,q\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

5
3
3
0
3