Background

This is a template problem.

Problem Description

Given a sequence, you will be asked multiple queries on an interval $[l,r]$. For each query, find the maximum distance between two equal numbers within the interval.

The distance between two elements in the sequence means the absolute difference of their indices.

Input Format

The first line contains an integer $n$, which is the length of the sequence.

The second line contains $n$ integers describing the sequence.

The third line contains an integer $m$, which is the number of queries.

Then follow $m$ lines, each containing two integers $l, r$, representing the query interval.

Output Format

Output $m$ lines. Each line contains one integer, the answer. If there are no two equal numbers in the interval, output $0$.

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

1
1
6
1
6

Hint

Let $a_i$ denote the elements of the sequence.

For $40\%$ of the testdata, $1\leq a_i \leq 400$, $1\leq n,m\leq 60000$.

For $100\%$ of the testdata, $1\leq n,m\leq 2\cdot 10^5$, $1\leq a_i\leq 2\cdot 10^9$。

Translated by ChatGPT 5