Challenge: How Many Passed?

Lab Java Beginner 10 points

Exam marks are given sorted. For each pass mark x, print how many students scored x or more. Use binary search to find the first mark that is at least x.

Input

Line 1: n. Line 2: n sorted marks (repeats allowed). Line 3: q. Line 4: q pass marks.

Output

One count per line.

Example

Input

7
35 50 50 50 72 88 91
4
50 60 0 100

Output

Sample input available Sample output available

Editor

Java

Hints

When a[mid] >= x, remember mid and keep looking left (hi = mid - 1).

If none qualify, the first position is n, which gives a count of 0.

Solution explanation

Count = n − (first index with mark ≥ x). O(log n) per question even with repeated marks.

Show solution

import java.util.Scanner;

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

    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(n - firstAtLeast(a, sc.nextInt())).append('\n');
        }
        System.out.print(sb);
    }
}

Output

Answer