1using System;
2using System.Collections.Generic;
3
4public class Solution {
5    public int[] MaxBeautyForQueries(int[][] items, int[] queries) {
6        Array.Sort(items, (a, b) => a[0] - b[0]);
7        int[] maxBeauties = new int[items.Length];
8        int maxBeauty = 0;
9
10        for (int i = 0; i < items.Length; i++) {
11            maxBeauty = Math.Max(maxBeauty, items[i][1]);
12            maxBeauties[i] = maxBeauty;
13        }
14
15        int[] result = new int[queries.Length];
16        for (int i = 0; i < queries.Length; i++) {
17            int idx = Array.BinarySearch(items, new int[]{queries[i], int.MaxValue}, Comparer<int[]>.Create((a, b) => a[0] - b[0]));
18            if (idx < 0) idx = ~idx - 1;
19            result[i] = idx >= 0 ? maxBeauties[idx] : 0;
20        }
21        return result;
22    }
23
24    public static void Main(string[] args) {
25        var solution = new Solution();
26        int[][] items = new int[][] { new int[] {1,2}, new int[] {3,2}, new int[] {2,4}, new int[] {5,6}, new int[] {3,5} };
27        int[] queries = new int[] { 1, 2, 3, 4, 5, 6 };
28        int[] result = solution.MaxBeautyForQueries(items, queries);
29        Console.WriteLine(string.Join(" ", result));
30    }
31}