Условие

Лайнландия представляет из себя одномерный мир, являющийся прямой, на котором располагаются N городов, последовательно пронумерованных от 0 до N - 1 . Направление в сторону от первого города к нулевому названо западным, а в обратную — восточным.

Когда в Лайнландии неожиданно начался кризис, все были жители мира стали испытывать глубокое смятение. По всей Лайнландии стали ходить слухи, что на востоке живётся лучше, чем на западе.

Так и началось Великое Лайнландское переселение. Обитатели мира целыми городами отправились на восток, покинув родные улицы, и двигались до тех пор, пока не приходили в город, в котором средняя цена проживания была меньше, чем в родном.

Примеры

Ввод: 10 1 2 3 2 1 4 2 5 3 1 Вывод: -1 4 3 4 -1 6 9 8 9 -1

Решение

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

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

    val n = reader.readLine().toInt() // Количество городов
    val prices = reader.readLine().trim().split(" ").map(String::toInt) // Средние цены проживания

    val stack = Stack<Int>()
    val result = IntArray(n) { -1 }

    for (i in 0 until n) {
        // Ищем город с меньшей ценой, чем текущий
        while (stack.isNotEmpty() && prices[stack.peek()] > prices[i]) {
            result[stack.pop()] = i
        }
        stack.push(i)
    }

    // Выводим номера городов для переселения
    writer.write(result.joinToString(" "))

    reader.close()
    writer.close()
}