1305 : 二分查找

Description

在给出的有序数组中查找特定数值的 Lower Bound 和 Upper Bound，在有序数组中，它们的定义分别是：

• Lower Bound：对于给定的元素 \(x\)，不小于 \(x\) 的第一个元素的位置
• Upper Bound：对于给定的元素 \(x\)，大于 \(x\)的第一个元素的位置

Input

第一行 \(1 \leq n \leq 10^7\) 与 \(1 \leq m \leq 100\)，表示 \(n\) 个元素的有序数组 \(a\) 和 \(m\) 次查询.

数组由如下代码定义：

for(int i = 0; i < n; i ++) {
    a[i] = (i == 0 ? 0 : a[i - 1]) + (int)(100 * sin(n + i)) % 3;
}

接下来 \(m\) 行每行一个整数表示查询的 \(x\).

Output

对于每个查询，输出空格隔开的 Lower Bound 和 Upper Bound 的数组下标，如果对应内容不存在则输出 -1.

Sample

6 5
3
9
2
1
11

##CASE##
6 6
7
6
3
0
0
5

2 2
-1 -1
1 2
1 1
-1 -1

##CASE##
-1 -1
3 -1
2 2
0 1
0 1
3 3

Hint

Source

Author

CSGrandeur