该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在小镇的科技庆典上，小明设计了一个名为“数字侦探”的趣味游戏，吸引了众多小伙伴参与。游戏中，小明准备了一个正整数数组，里面藏有许多神秘的数字线索。每位小侦探面临的挑战是，根据给出的查询要求，追踪特定数字在过去出现的位置。

你将获得一个由不超过$10^5$范围的正整数组成的列表nums，该列表下标从1开始，列表的长度不会超过$10^6$。接下来，会有一系列的查询请求到来，每个请求以形式x y给出，意味着你需要查找数字y最后一次出现在位置x之前的下标。

比如，如果nums=[1,2,3,2,5]，当查询为3 2时，因为2在位置3之前最后一次出现在位置2，所以答案是2。但如果之前没有出现过y，则输出-1。

作为小明邀请的小小侦探，你的目标是快速响应每一个查询，精准找出或确定数字y在指定位置x之前最后一次现身的位置下标，揭开隐藏在数组背后的秘密。

输入格式

第一行包含两个整数n和m，表示数组的长度和询问的次数。

第二行包含n个整数，表示数组的n个元素。

姐姐下来m行包含m次询问，操作输入格式为: x y，表示你需要查找数字y最后一次出现在位置x之前的下标。如果不存在，则输出-1。

输出格式

输出m行，对于每次询问输出答案。

数据范围

对于40%的数据，$1\leq{n,m}\leq10$；

对于60%的数据，$1\leq{n,m}\leq1000$，保证每个数的出现次数不超过10次；

对于100%的数据，$1\leq{n,m}\leq1000000$。

样例

5 2
1 2 3 2 5
3 2 
3 5

2
-1

4 1
1 1 1 2
4 1

3

Limitation

1500ms，524288K