题目描述

给定 $n$ 个正整数a[1...n]，对于一个正整数 $x$，其”前驱“定义为 $n$ 个数中满足 $<x$ 的数中的最大值。

给定 $x$，请你找到 $x$ 的前驱是哪个数，输出这个数的下标和值（若有多个取下标最小的）。

一共有 $q$ 次询问。

例如 $n$ 个数 a = [6,3,4,1,1]，4的前驱为a[2] = 3，2的前驱为a[4]=1（值相同取下标最小的）。

输入格式

第一行包含1个整数 $n$，代表数组长度。

第二行包含 $n$ 个正整数a[1...n]，空格隔开。

第三行包含1个整数 $q$，代表有 $q$ 组询问。

第四行包含 $q$ 个正整数，表示每组询问需要查找的 $x$ 值，空格隔开。

输出格式

输出 $q$ 行，每行2个整数，代表答案的下标和值（若有多个取下标最小的）；特别的，若前驱不存在本行输出-1。

样例

样例输入1

5
6 3 4 1 1
5
4 2 1 10 5

样例输出1

2 3
4 1
-1
1 6
3 4

样例输入2

3
6397341258964956834925482398592385 3123945691285933452452345252431395195 4398618904569135589459884937
2
347856278934567892345984567249569465924659448572934589 38467389246783746836

样例输出2

2 3123945691285933452452345252431395195
-1

数据范围

对于20%的数据，$n,q,x,a[i]<=10$，且 $x$ 保证在 a[1...n] 中出现过。

对于40%的数据，$n,q,x,a[i]<=1000$。

对于另30%的数据，$n,q<=1000, 1<=x,a[i]<=10^{50}$。

对于100%的数据，$n,q<=10^5, 1<=x,a[i]<=10^{50}$。