Challenge: Roll Call

Lab Java Beginner 10 points

A teacher has the sorted roll numbers of n students. For each of q numbers called out, print the index where it sits (from 0), or -1 if no such student. Write your own binary search.

Input

Line 1: n. Line 2: n sorted, different numbers. Line 3: q. Line 4: q numbers.

Output

One answer per line.

Example

Input

6
3 8 12 19 25 31
4
19 3 31 20

Output

Sample input available Sample output available

Editor

Java

Hints

lo = 0, hi = n - 1, loop while lo <= hi.

Middle too small → lo = mid + 1. Too big → hi = mid - 1.

Solution explanation

Each question takes O(log n), so all of them take O(q log n).

Show solution

import java.util.Scanner;

public class Main {
    static int search(int[] a, int x) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] == x) return mid;
            if (a[mid] < x) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int q = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) sb.append(search(a, sc.nextInt())).append('\n');
        System.out.print(sb);
    }
}

Output

Answer