镜像（弱化版）

题目描述:

小 W 走出了无尽迷宫，习得新技能 “镜像” ，可以在战胜对手后复制对手的能力。

这一天，他来到了角斗场，角斗场里有 n 个斗士， 编号为 i 的斗士战斗力为 a_i 。由于小 W 战斗技巧娴熟，他可以战胜战斗力不超过他两倍的敌人，同时在战胜战斗力为 x 的敌人后可以将自身战斗力变为 x 。

接下来小 W 有 q 次询问，每次询问给出 l,r,x,k ，他想要知道当他初始战斗力为 x 时，能否战胜编号在 [l,r] 的所有敌人。小 W 的战斗策略十分简单，他每次会和他能战胜的敌人中编号最小的敌人战斗。若对手的战斗力大于小 W ，小 W 便会镜像对手，使自己战斗力变得与对手相同。如果小 W 可以战胜所有对手，请输出他打败的第 k 个斗士的编号，否则请输出 -1 。

输入格式:

第一行一个整数 n ，表示斗士数量。

接下来一行用 n 个用空格分隔的整数 a_i，表示第 i 个斗士的能力值。

第 n+2 行有一个整数 q ，表示询问个数。

接下来 q 行每行四个整数 l,r,x,k ，表示一组询问。

输出格式:

 q 行每行一个整数，表示每组询问的答案

样例输入:

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

样例输出:

1
3
-1
4

提示:

对于样例1:

- 第一次询问：小 W 的初始战斗力为 1 时的策略为 {2,1,4,3,5} 输出第二个为 1
- 第二次询问：策略为 {4,3,5} 
- 第三次询问：小 W 的初始战斗力不足以让其击败任何一个对手
- 第四次询问：小 W 可以打败任何一个敌人，所以策略为{1,2,3,4,5} 

【数据范围】

-  对于 33% 的数据 n,q ≤ 100
-  对于 100% 的数据 n,q ≤ 1000, k ∈ [1,r-l+1]， 1 ≤ a_i,x ≤ 10^9， 1 ≤ l ≤ r ≤ n

有能力的同学可以尝试用c++做n≤100000，q≤23333的部分即这道题

出题人提醒:注意时间复杂度

时间限制: 1000ms
空间限制: 256MB

---

来源: lindu