Migrated from Lutece 1015 Lweb and pepper

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Lweb学长是一个最讨厌花椒的学长，有一天他突发奇想要请全集训队的人吃饭。

来到饭店，看到饭店里总共用$n$道菜，每道菜都有一个编号$i（0 \leq i < n）$,他是如此的讨厌花椒，他看着菜单肉眼估计着每一道菜含有花椒的可能性$p$,但身处大四川，他得顾及到一些爱吃花椒的小伙伴，他盘算着要让这一桌子菜里有且仅有一道含有花椒的菜。

但是在他陷入沉思的时候，忽然发现，周边的小伙伴已经选择了编号从$L$到$R$的这些菜，Lweb学长看着菜单，决定再点一道菜，同时为了掌控一下局势，他需要计算一下应该选择哪一道菜，可以使得有且仅有一道菜含有花椒的可能性最大。

Lweb学长没有太长的思索时间，需要一个机智的小伙伴来帮他做决定。

Input

第一行输入一个$T$，表示测试数据组数。

每组数据包含$3+m$行

第一行给出一个整数$n$，表示菜的总数$(1< n \leq 100000)$。

第二行有$n$个实数，分别表示$p_0,p_1,p_2,⋯⋯,p_{n-1}. (0 < p_i < 1)$

第三行给出一个整数$m$，表示有多少个询问$(1 < m \leq 1000)$。

接下来的$m$行，每行有两个整数，$L$ 和 $R$ 表示Lweb学长的小伙伴已经选择了编号为$L,L+1，L+2, \cdots,R$这些菜。$（ 0 \leq L \leq R < n, R-L<min(1000,n-1) ）$

Output

对于每一个询问,输出一个整数k，表示选了编号为k的这道菜，可以使得 有且仅有 一道菜含有花椒的概率最大,如果有多个选择，输出序号最小的那一个 （输入有$m$个询问，则有$m$个输出）

Samples

2
4
0.1 0.2 0.8 0.8
2
1 3 
2 3
4
0 0 0 0
2
1 3
2 3

0
0
0
0

Note

小朋友们不用担心精度问题，为了避免精度误差导致的一些错误，数据出的很良心。

Resources

icerain