3107: beautiful

一个长度为 n 的序列,对于每个位置 i 的数 a i 都有一个优美值,其定义是:找到序列中最 长的一段 [l, r],满足 l ≤ i ≤ r,且 [l, r] 中位数为 a i (我们比较序列中两个位置的数的大小时, 以数值为第一关键字,下标为第二关键字比较。这样的话 [l, r] 的长度只有可能是奇数),r - l + 1 就是 i 的优美值。 接下来有 Q 个询问,每个询问 [l, r] 表示查询区间 [l, r] 内优美值的最大值。

第一行输入 n 接下来 n 个整数,代表 a i 接下来 Q,代表有 Q 个区间接下来 Q 行,每行 两个整数 l, r(l ≤ r),表示区间的左右端点

对于每个区间的询问,输出答案

8
16 19 7 8 9 11 20 16
8
3 8
1 4
2 3
1 1
5 5
1 2
2 8
7 8

7
3
1
3
5
3
7
3