有 n 位同学按照年龄从小到大排好队。
王老师想要查询,年龄为 x 的同学,在队伍中首次出现的位置和最后一次出现的位置;如果队伍中不存在年龄为 x 的同学,请输出 -1。
由于人数太多,一个一个数,太慢啦,请你编程求解。
请注意:本题中王老师查询年龄 x 出现的起止位置,并不是查询了 1 次,而是查询了 q 次。
比如:
假设有 6 位同学的年龄为:1 2 2 2 3 3,王老师查询了 4 个年龄,分别是 2 1 3 8 ,那么:
年龄为 2 的同学首次和最后一次出现的位置分别是:2 4;
年龄为 1 的同学首次和最后一次出现的位置分别是:1 1;
年龄为 3 的同学首次和最后一次出现的位置分别是:5 6;
年龄为 8 的同学首次和最后一次出现的位置分别是:-1 -1;
第一行包含整数 n 和 q ,表示队伍中的总人数和询问个数。
第二行包含 n 个整数(整数的值均在 1 \sim 10000 范围内),表示队伍中每个人的年龄。
接下来 q 行,每行包含一个整数 x ,表示一次询问的值。
共 q 行,每行包含两个整数,表示所求年龄在队伍中的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1
。
数据范围
1≤n≤100000,1≤q≤10000,1≤x≤10000。
6 3 1 2 2 2 3 3 2 1 8
2 4 1 1 -1 -1
二分