class Solution {
    fun isTrionic(nums: IntArray): Boolean {
        val n = nums.size
        for (p in 1 until n - 2) {
            if (nums[p] <= nums[p - 1]) continue
            for (q in p + 1 until n - 1) {
                if (nums[q] >= nums[q - 1]) break
                if (nums[q] < nums[q - 1] && nums[q] < nums[q + 1]) {
                    var valid = true

                    for (i in 0 until p)
                        if (nums[i] >= nums[i + 1]) {
                            valid = false
                            break
                        }

                    for (i in p until q)
                        if (nums[i] <= nums[i + 1]) {
                            valid = false
                            break
                        }

                    for (i in q until n - 1)
                        if (nums[i] >= nums[i + 1]) {
                            valid = false
                            break
                        }

                    if (valid) return true
                }
            }
        }
        return false
    }
}

class Solution {
    fun maxBalancedShipments(weight: IntArray): Int {
        var i = 0
        val n = weight.size
        var count = 0

        while (i < n) {
            var max = weight[i]
            var found = false

            for (j in i + 1 until n) {
                max = maxOf(max, weight[j])
                if (weight[j] < max) {
                    count++
                    i = j + 1
                    found = true
                    break
                }
            }

            if (!found) break
        }

        return count
    }
}

class Solution {
    fun minTime(s: String, order: IntArray, k: Int): Int {
        val n = s.length
        val isStar = BooleanArray(n)
        val nostevanik = s.toCharArray()

        val totalSubstrings = n.toLong() * (n + 1) / 2

        val segTree = java.util.TreeSet<Int>()
        segTree.add(-1)
        segTree.add(n)

        var nonStarSum = totalSubstrings

        for (t in order.indices) {
            val idx = order[t]
            isStar[idx] = true
            nostevanik[idx] = '*'

            val right = segTree.higher(idx)!!
            val left = segTree.lower(idx)!!

            val oldLen = (right - left - 1).toLong()
            val leftLen = (idx - left - 1).toLong()
            val rightLen = (right - idx - 1).toLong()

            nonStarSum -= oldLen * (oldLen + 1) / 2
            if (leftLen > 0) nonStarSum += leftLen * (leftLen + 1) / 2
            if (rightLen > 0) nonStarSum += rightLen * (rightLen + 1) / 2

            segTree.add(idx)

            val validSubstrings = totalSubstrings - nonStarSum
            if (validSubstrings >= k) return t
        }

        return -1
    }
}