Условие

Диего увлекается коллекционированием наклеек. На каждой из них написано число, и каждый коллекционер мечтает собрать наклейки со всеми встречающимися числами.

Диего собрал N наклеек, некоторые из которых, возможно, совпадают. Как-то раз к нему пришли K коллекционеров. i-й из них собрал все наклейки с номерами не меньшими, чем pᵢ. Напишите программу, которая поможет каждому из коллекционеров определить, сколько недостающих ему наклеек есть у Диего. Разумеется, гостей Диего не интересуют повторные экземпляры наклеек.

Примеры

Ввод: 1 5 2 4 6 Вывод:

0 1

Ввод: 3 100 1 50 3 300 0 75 Вывод:

3 0 2

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val n = reader.readLine().toInt() // Читаем количество наклеек у Диего
    
    // Читаем наклейки Диего, удаляя дубликаты и сортируя
    val diegoStickers = if (n > 0) reader.readLine().split(" ").map { it.toInt() }.toSortedSet().toList() else emptyList()

    val k = reader.readLine().toInt() // Читаем количество запросов
    
    // Читаем запросы коллекционеров
    val collectors = if (k > 0) reader.readLine().split(" ").map { it.toInt() } else emptyList()

    // Для каждого запроса выполняем бинарный поиск
    for (pi in collectors) {
        val index = diegoStickers.binarySearch(pi).let { if (it < 0) -it - 1 else it } // Находим количество уникальных наклеек, меньших pi
        writer.write("$index\\n")
    }

    reader.close()
    writer.flush()
    writer.close()
}