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