题目描述

在数学统计课程中，Bob 想出了一种新的方法来计算长度为奇数的数组的“平均值”。

只要数组长度大于 1，就执行如下操作：选择数组中任意一个长度为 3 的连续段 $[l,r]$，其中 $r=l+2$，计算这三个元素的中位数，并用一个等于该中位数的元素替换这三个元素。

三个数的中位数是第二大的数。例如 $[1,5,4]$ 的中位数是 $4$，$[2,2,2]$ 的中位数是 $2$。

例如数组 $[4,1,3,2,5]$ 的一种处理方式为：

Bob 发现这种方法没有唯一定义：不同的选择顺序可能得到不同结果。为了解决这个问题，他规定：每次选择长度为 3 的段时，都可以为了让最终剩下的唯一数字尽可能大而选择。这个最大可能的最终数字称为该数组的 Bob 平均数。

给定一个数组 $a$，需要回答 $q$ 个查询。第 $j$ 个查询给出区间 $[L_j,R_j]$，要求输出原数组该区间的 Bob 平均数。保证每个查询区间长度为奇数。

输入格式

第一行包含整数 $n$：

第二行包含 $n$ 个整数 $a_i$：

第三行包含整数 $q$：

接下来 $q$ 行，每行包含两个整数 $L_j,R_j$：

并保证 $R_j-L_j+1$ 为奇数。

输出格式

对每个查询输出一行一个整数，表示该区间的 Bob 平均数。

样例

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

2
4
4
3
4