#M085. 【模板】回滚莫队&不删除莫队

    ID: 6053 传统题 1000ms 256MiB 尝试: 6 已通过: 4 难度: 6 上传者: 标签>CF2000提高回滚莫队只增不减维护回滚维护状态离散化稀疏状态重置

【模板】回滚莫队&不删除莫队

题目背景

这是一道模板题。

题目描述

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

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

输入格式

第一行一个整数 nn,表示序列长度。

第二行 nn 个整数,描述这个序列。

第三行一个整数 mm,表示询问个数。

之后 mm 行,每行两个整数 l,rl,r 表示询问区间。

输出格式

共 mm 行,每行一个整数表示答案。如果区间内不存在两个数相同,则输出 00。

样例 #1

样例输入 #1

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

样例输出 #1

1
1
6
1
6

提示

记 aia_i 表示序列元素。

对于 40%40\% 的数据,满足 1≤ai≤4001\leq a_i \leq 400,1≤n,m≤600001\leq n,m\leq 60000。

对于 100%100\% 的数据,满足 1≤n,m≤2⋅1051\leq n,m\leq 2\cdot 10^5,1≤ai≤2⋅1091\leq a_i\leq 2\cdot 10^9。