题目描述

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

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

• 3 第一次出现在第 5 位
• 2 第一次出现在第 2 位
• 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

输出样例

5 2 -1

题目要求

• 必须使用二分查找（时间复杂度 O(q log n)）
• 数组下标从 1 开始
• 多组查询，需要高效运行