#B4419. 查找最后一个出现的位置

查找最后一个出现的位置

题目描述

输入一个长度为 nn非递减正整数数列 a1,a2,,ana_1,a_2,\dots,a_{n},然后进行 mm 次询问。对于每次询问,给出一个整数 qq,要求输出这个数字在序列中最后一次出现的下标。如果序列中不包含该数字,请输出 1-1

注意:下标从 1 开始。

输入格式

第一行,包含两个正整数 nnmm,分别表示数列的长度和询问的次数。

第二行,包含 nn 个正整数 a1,a2,,ana_1, a_2, \ldots, a_n

接下来 mm 行,每行包含一个正整数 qq,表示一次询问。

输出格式

输出共 mm 行。

对于每次询问,如果数字 qq 存在于数列中,则输出它在数列中最后一次出现的下标;如果不存在,则输出 1-1

8 5
2 3 5 5 5 8 9 9
5
2
9
6
8
5
1
8
-1
6

提示

样例解释

数列为 [2,3,5,5,5,8,9,9][2, 3, 5, 5, 5, 8, 9, 9]

  1. 询问 55:数字 5 最后一次出现在第 5 个位置。
  2. 询问 22:数字 2 最后一次出现在第 1 个位置。
  3. 询问 99:数字 9 最后一次出现在第 8 个位置。
  4. 询问 66:数列中不存在 6。
  5. 询问 88:数字 8 最后一次出现在第 6 个位置。

数据范围

对于所有测试点,保证:

  • 1n,m1061 \leq n, m \leq 10^6
  • 1ai,q1091 \leq a_i, q \leq 10^9
  • 对于 1i<n1 \leq i < n,保证 aiai+1a_i \leq a_{i+1}

本题输入输出量较大,请使用较快的 IO 方式。