题目描述

给定一个非递减有序数组（数组中包含重复元素），使用二分查找完成多次查询： 对于每个查询值 x，找到它最后一次出现的位置（数组下标从 1 开始）。 如果数组中不存在 x，输出 -1。

示例： 数组：1 2 2 2 3 3 查询：3 2 5 答案：6 4 -1

• 3 最后一次出现在第 6 位
• 2 最后一次出现在第 4 位
• 5 不存在，输出 -1

输入格式

1. 第一行：一个整数 n，表示数组元素个数（n ≤ 10^5）
2. 第二行：n 个非递减整数，表示数组元素
3. 第三行：一个整数 q，表示查询次数（q ≤ 10^5）
4. 第四行：q 个整数，表示每次需要查询的数值 x

输出格式

输出一行，包含 q 个整数，依次表示每个查询值最后一次出现的位置；若不存在，输出 -1。

输入样例

6
1 2 2 2 3 3
3
3 2 5

输出样例

6 4 -1

说明/提示

• 数组下标从 1 开始
• 必须使用二分查找，保证时间复杂度：$O(q \log n)$
• 数据量大，必须使用输入输出加速