题目描述

给定整数序列 $a_1,a_2,\dots,a_n$。

给去q次查询，每次查询为区间 $[l,r]$，其中 $1 \le l \le r \le n$。

子区间中位数定义

将子区间内数字从小到大排序：

1. 区间长度为奇数：中位数是排序后正中间的数字；
2. 区间长度为偶数：中位数取排序后居中两个数字里更大的那一个。

输入格式

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

第二行共 $n$ 个整数，为序列 $a_1,a_2,\dots,a_n$。

第三行一个整数 $q$，为查询次数。

接下来的第 $i$ 行两个整数 $l_i$ 和 $r_i$，为第 $i$ 个查询的区间 $[l_i,r_i]$。

输出格式

输出 $q$ 行，每行一个整数，为对应查询的区间中位数。

样例输入

5
1 2 3 4 5
3
1 3
2 4
3 5

样例输出

 2
 3
 4

数据范围

• $1 \le n,q \le 10^5$
• $0 \le a_i \le 10^9$