U182500 beautiful

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

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

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

对于 30% 的数据，满足 n，Q ≤ 50 对于 70% 的数据，满足 n，Q ≤ 2000 对于所有数据，满足 n ≤ 2000, Q ≤ 100000,ai ≤ 200