Find each value

Problem

A sorted list of distinct product codes is given, followed by some queries. For each query print its position (counting from 0) in the list, or -1 when it is not there. The starter holds a program with a bug. Find it and fix it.

Input, output and limits

Input: Line 1: n. Line 2: n sorted integers. Line 3: q. Line 4: q integers to look up.
Output: q lines, each the position or -1.
Constraints: 1 ≤ n, q ≤ 1000
The list is strictly increasing
-100000 ≤ each value ≤ 100000

Examples

Example

Input

5
10 20 30 40 50
3
30 35 10

Output

2
-1
0

Hints

Try the problem first. Open one hint at a time.

Hint 1

Halve the search range each time, as binary search does.

Hint 2

A range with one item left must still be checked.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Balanced bracketsmedium
Best stretch of markshard
Rotate right by kmedium
Pairs with a given sumhard
Remove duplicates, keep the firstmedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Testing Your Solutions problems

Problem

Input, output and limits

Examples

Hints

More Testing Your Solutions problems