题目描述

给定一个正整数 $n$ 和含有 $n$ 个单调不减的元素的数组 $a$ 。

进行 $q$ 次询问，每次给定一个目标值 $x$ ，查询返回 $>= x$ 的第一个位置和 $>x$ 的第一个位置。

注：本题关于下标位置的编号从 $1$ 开始记录。

输入格式

第一行输入一个正整数 $n$ ，代表数组大小。

第二行输入 $n$ 个正整数，为单调不减的数组 $a$ 的元素。

第三行输入一个正整数 $q$ ，代表询问次数。

接下来 $q$ 行，每行一个正整数 $x$ ，代表要被询问的目标值。

输出 $q$ 行答案，每行两个正整数，为 $>= x$ 的第一个位置和 $>x$ 的第一个位置。

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

3 7
10 11

对于 $100\%$ 的数据：

$1\leq n \leq 10^6$

$1\leq a_1 \leq a_2 \leq \dots \leq a_{n-1} \leq a_n \leq 10^9$

$1\leq q \leq 10^6$

$1\leq x \leq 10^9$