谎言即是爱

『 露比...阿库亚...我爱你们...啊...终于说出口了...对不起...这句话妈妈说的太晚了...太好了...这句话...绝对...不是谎言...  』

给定一个长度为N的序列A，q次询问，每次询问给定 [l，r] 表示区间左右端点。对于每次询问，请你求出对于任意的x， ∑|x-A_i|（l<=i<=r） 的最小值。

你需要输出满足条件的x和上式的最小值，用空格隔开。如果有多个满足条件的x，输出最小的那个。

第一行一个整数 N  ( 1 ≤ N ≤ 10⁵ )代表序列长度。

接下来一行有N个正整数 A_i ( 1 ≤ A_i ≤ 10⁹) , 用空格隔开。

接下来一行一个整数 q , (1≤ q ≤10⁵) 代表询问的区间次数。

接下来 q 行，每行一个区间l , r ( 1 ≤ l ≤ r ≤ N )

输出Q Q q 行。每行代表对应询问的结果

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

2 1
3 0
3 2