题目描述

请在一个有序不递减的数组中（数组中的值有相等的值），采用二分查找，找到第 1 个大于或等于元素 x 的位置，如果不存在，请输出 -1 。

请注意：本题要求出 q 个 x ，每个 x 在数组找到第1个大于或等于 x 的元素的位置。

比如有 6 个数，分别是： 1 2 2 2 6 6 ，那么如果要求 3 个数： 5 8 2 ，在数组中找到第 1 个大于或等于他们的位置，答案是： 5 -1 2 。

输入格式

第一行，一个整数 n ，代表数组元素个数( n <= ${10}^5$ )

第二行，n 个整数，用空格隔开，代表数组的 n 个元素( 1 <= 数组元素的值 <= ${10}^8$ )

第三行，一个整数q，代表有要查询q个数( q <= ${10}^5$ )

第四行，q 个整数，用空格隔开，代表查询的数( 1 <= 要找的数 <= ${10}^8$ )

输出格式

按题意输出位置或者 -1 。

样例

6
1 2 2 2 6 6
3
5 8 2

5 -1 2