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
    }
}