Equal Range

要素が昇順にソートされた数列 $A = \{a_0, a_1, ..., a_{n-1}\}$ に対して、クエリとして与えられた値$k$のlower bound とupper bound の組を求めてください。

• lower bound: 指定された値以上の値が現れる最初の位置 ($k \leq a_i$となるような最小の$i$)。存在しない場合は$n$とする。
• upper bound: 指定された値より大きい値が現れる最初の位置($k < a_i$となるような最小の$i$)。存在しない場合は$n$とする。

Input

入力は以下の形式で与えられます。

$n$
$a_0 \; a_1 \; ,..., \; a_{n-1}$
$q$
$k_1$
$k_2$
:
$k_q$

１行目に数列の要素数$n$、２行目に数列の各要素$a_i$ が与えられます。

３行目にクエリの数$q$、続く$q$行に各クエリの値$k_i$が与えられます。

Output

各クエリに対して、lower bound $l$ ($l = 0, 1, ..., n$)とupper bound $r$ ($r = 0, 1, ..., n$)を空白で区切って１行に出力してください。

Constraints

• $1 \leq n \leq 100,000$
• $1 \leq q \leq 200,000$
• $0 \leq a_0 \leq a_1 \leq ... \leq a_{n-1} \leq 1,000,000,000$
• $0 \leq k_i \leq 1,000,000,000$

Sample Input 1

4
1 2 2 4
3
2
3
5

Sample Output 1

1 3
3 3
4 4

---

Source: https://onlinejudge.u-aizu.ac.jp/problems/ITP2_6_D