Условие

В Берляндии есть проспект Берленина, по которому ходит автобус. Проспект можно считать прямой, вдоль которой введена система координат. Всего на проспекте есть n остановок, i-я из которых находится в точке с координатой a_i.

Паша пишет новое приложение для отслеживания автобусов и хочет рисовать иконку автобуса около ближайшей остановки. Формально, если автобус имеет координату x, то выбирается номер остановки i, минимизирующий | a_i – x |. Если таких i несколько, то Паша выбирает номер нужной остановки по очень странным правилам:

• Если есть остановки, совпадающие с координатой автобуса, то стоит вывести минимальную по номеру среди них.

• Если есть остановки справа и слева, то стоит вывести максимальную по номеру среди левых.

• Если есть остановки только слева, то стоит вывести максимальную по номеру среди левых.

• Если есть остановки только справа, то стоит вывести минимальную по номеру среди правых.

Пашино приложение ещё не готово до конца, поэтому он просит вас помочь разработать эту функциональность. Для теста он выдал вам k запросов, каждый из которых задаётся числом x — координатой автобуса.

Примеры

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

2 1

Решение

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

fun main(args: Array<String>) {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    // Читаем входные данные
    val (n, k) = reader.readLine().split(" ").map { it.toInt() }
    val stops = reader.readLine().split(" ").map { it.toLong() }
    val queries = reader.readLine().split(" ").map { it.toLong() }

    // Обрабатываем каждый запрос
    for (x in queries) {
        // Бинарный поиск ближайшей остановки
        var left = 0
        var right = n - 1
        
        while (left <= right) {
            val mid = (left + right) / 2
            if (stops[mid] == x) {
                // Если нашли точное совпадение, ищем минимальный индекс
                var result = mid
                while (result > 0 && stops[result - 1] == x) {
                    result--
                }
                writer.write("${result + 1}\\n")
                break
            } else if (stops[mid] < x) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        // Если точного совпадения нет
        if (left > right) {
            val leftIndex = right  // последняя остановка слева
            val rightIndex = left  // первая остановка справа
            
            when {
                // Нет остановок слева
                leftIndex < 0 -> writer.write("${rightIndex + 1}\\n")
                // Нет остановок справа
                rightIndex >= n -> writer.write("${leftIndex + 1}\\n")
                else -> {
                    val leftDist = x - stops[leftIndex]
                    val rightDist = stops[rightIndex] - x
                    
                    when {
                        // Одинаковое расстояние до левой и правой
                        leftDist == rightDist -> writer.write("${leftIndex + 1}\\n")
                        // Ближе левая
                        leftDist < rightDist -> writer.write("${leftIndex + 1}\\n")
                        // Ближе правая
                        else -> writer.write("${rightIndex + 1}\\n")
                    }
                }
            }
        }
    }

    reader.close()
    writer.close()
}