Условие

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.

Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика). Напишите программу, определяющую, можно ли это сделать.

Примеры

Ввод: 3 3 2 1 Вывод: YES

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

Ввод: 3 2 3 1 Вывод: NO

Решение

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 cars = reader.readLine().trim().split(" ").map(String::toInt) // Порядок вагонов

    val stack = Stack<Int>()
    var current = 1

    for (car in cars) {
        stack.push(car) // Помещаем вагон в тупик

        // Пока верхний вагон соответствует ожидаемому номеру, убираем его
        while (stack.isNotEmpty() && stack.peek() == current) {
            stack.pop()
            current++
        }
    }

    // Если все вагоны упорядочены, выводим YES, иначе NO
    writer.write(if (stack.isEmpty()) "YES" else "NO")

    reader.close()
    writer.close()
}