2078 - 起止位置

题目描述

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

输入

第一行包含整数 nq ,表示队伍中的总人数和询问个数。

第二行包含 n 个整数(整数的值均在 1 \sim 10000 范围内),表示队伍中每个人的年龄。

接下来 q 行,每行包含一个整数 x ,表示一次询问的值。

输出

q 行,每行包含两个整数,表示所求年龄在队伍中的起始位置和终止位置。

如果数组中不存在该元素,则返回 -1 -1

样例

输入

6 3
1 2 2 2 3 3
2
1
8

输出

2 4
1 1
-1 -1
说明

数据范围

1≤n≤100000,1≤q≤10000,1≤x≤10000

来源

二分

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1916
通过人数 1104
金币数量 1 枚
难度 入门


上一题 下一题