1import java.util.*;
2
3class Solution {
4    public int[] maxBeautyForQueries(int[][] items, int[] queries) {
5        Arrays.sort(items, (a, b) -> a[0] - b[0]);
6        int[] maxBeauties = new int[items.length];
7        int maxBeauty = 0;
8
9        for (int i = 0; i < items.length; i++) {
10            maxBeauty = Math.max(maxBeauty, items[i][1]);
11            maxBeauties[i] = maxBeauty;
12        }
13
14        int[] result = new int[queries.length];
15        for (int i = 0; i < queries.length; i++) {
16            int idx = Arrays.binarySearch(items, new int[]{queries[i], Integer.MAX_VALUE}, Comparator.comparingInt(a -> a[0]));
17            if (idx < 0) idx = -idx - 2;
18            result[i] = idx >= 0 ? maxBeauties[idx] : 0;
19        }
20
21        return result;
22    }
23
24    public static void main(String[] args) {
25        Solution sol = new Solution();
26        int[][] items = {{1,2}, {3,2}, {2,4}, {5,6}, {3,5}};
27        int[] queries = {1, 2, 3, 4, 5, 6};
28        int[] result = sol.maxBeautyForQueries(items, queries);
29        System.out.println(Arrays.toString(result));
30    }
31}