题目背景

这是一道模板题。

题目描述

给定一个序列，多次询问一段区间 $[l,r]$，求区间中相同的数的最远间隔距离。

序列中两个元素的间隔距离指的是两个元素下标差的绝对值。

输入格式

第一行一个整数 $n$，表示序列长度。

第二行 $n$ 个整数，描述这个序列。

第三行一个整数 $m$，表示询问个数。

之后 $m$ 行，每行两个整数 $l,r$ 表示询问区间。

输出格式

共 $m$ 行，每行一个整数表示答案。如果区间内不存在两个数相同，则输出 $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

提示

记 $a_i$ 表示序列元素。

对于 $40\%$ 的数据，满足 $1\leq a_i \leq 400$，$1\leq n,m\leq 60000$。

对于 $100\%$ 的数据，满足 $1\leq n,m\leq 2\cdot 10^5$，$1\leq a_i\leq 2\cdot 10^9$。