You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

给出一个从递增的正整数序列a0,a1……an-1 对不同的查询输出对应结果

Input

单组数据 第一行是一个整数n，代表序列的长度（下标从0开始一直到n-1） 接下来n个整数，代表序列对应位置上的数 再接下来一行是一个整数m代表查询次数 接下来m行 接下来的每行是这5种类型之一 0 x 代表查询数字x出现的最大下标，若不存在x输出-1 1 x 代表查询数字x出现的最小下标，若不存在x输出-1 2 x y 代表查询大于等于x且小于等于y的数字的个数，并保证x<=y 3 x 代表查询比x大且下标最小的数字的大小，若不存在比x大的数字输出-1 4 x 代表查询比x小且下标最大的数字的大小，若不存在比x小的数字输出-1 n,m<1e5 $0<=ai,x,y<10^9$

Output

输出对应结果，每个结果占一行

Samples

10 
1 1 1 3 4 5 5 5 5 8
5
0 5
1 5
2 1 5
3 4
4 8

8
5
9
5
5

Limitation

1s, 1024KiB for each test case.