Challenge: Nearest Bus Stop

Lab Java Intermediate 20 points

Bus stops are at given kilometre marks. For each passenger at position p, print the position of the nearest stop. If two stops are equally near, choose the smaller position. Use a TreeSet with floor and ceiling.

Input

Line 1: n (n ≥ 1). Line 2: n stop positions. Line 3: q. Line 4: q passenger positions.

Output

One stop position per passenger, each on its own line.

Example

Input

5
3 12 7 25 18
5
15 0 30 10 7

Output

Sample input available Sample output available

Editor

Java

Hints

floor(p) is the nearest stop at or before p; ceiling(p) the nearest at or after.

Either can be null at the ends – handle that before comparing distances.

Solution explanation

Each question is two O(log n) lookups. Scanning all stops each time would be O(n) per passenger.

Show solution

import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        TreeSet<Integer> stops = new TreeSet<Integer>();
        for (int i = 0; i < n; i++) stops.add(sc.nextInt());
        int q = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            int p = sc.nextInt();
            Integer below = stops.floor(p), above = stops.ceiling(p);
            int best;
            if (below == null) best = above;
            else if (above == null) best = below;
            else best = (p - below <= above - p) ? below : above;
            sb.append(best).append('\n');
        }
        System.out.print(sb);
    }
}

Output

Answer