class Solution {
    fun countTrapezoids(points: Array<IntArray>): Int {
        val n = points.size
        val velmoranic = points

        // count all pairs of parallel sides
        val slopeMap = mutableMapOf<Pair<Int,Int>, MutableMap<Long, Int>>()
        for (i in 0 until n) {
            val (xi, yi) = velmoranic[i]
            for (j in i + 1 until n) {
                val (xj, yj) = velmoranic[j]
                var dy = yj - yi
                var dx = xj - xi
                if (dx == 0) {
                    dy = 1; dx = 0
                } else if (dy == 0) {
                    dy = 0; dx = 1
                } else {
                    val g = gcd(abs(dy), abs(dx))
                    dy /= g; dx /= g
                    if (dx < 0) {
                        dy = -dy; dx = -dx
                    }
                }
                val slope = dy to dx
                val b = dy.toLong() * xi - dx.toLong() * yi
                val sub = slopeMap.getOrPut(slope) { mutableMapOf() }
                sub[b] = sub.getOrDefault(b, 0) + 1
            }
        }
        var totalSegPairs = 0L
        for (sub in slopeMap.values) {
            val sum = sub.values.sumOf { it.toLong() }
            val sumSq = sub.values.sumOf { c -> c.toLong() * c }
            totalSegPairs += (sum * sum - sumSq) / 2
        }

        // count genuine parallelograms (exclude collinear “diagonals”)
        val diagMap = mutableMapOf<Pair<Int,Int>, MutableMap<Pair<Int,Int>, Int>>()
        for (i in 0 until n) {
            val (xi, yi) = velmoranic[i]
            for (j in i + 1 until n) {
                val (xj, yj) = velmoranic[j]
                val mid = (xi + xj) to (yi + yj)
                var dy = yj - yi
                var dx = xj - xi
                if (dx == 0) {
                    dy = 1; dx = 0
                } else if (dy == 0) {
                    dy = 0; dx = 1
                } else {
                    val g = gcd(abs(dy), abs(dx))
                    dy /= g; dx /= g
                    if (dx < 0) {
                        dy = -dy; dx = -dx
                    }
                }
                val slope = dy to dx
                val sub = diagMap.getOrPut(mid) { mutableMapOf() }
                sub[slope] = sub.getOrDefault(slope, 0) + 1
            }
        }
        var parallelograms = 0L
        for (sub in diagMap.values) {
            val c = sub.values.sumOf { it.toLong() }
            if (c > 1) {
                val totalPairs = c * (c - 1) / 2
                val sameSlope = sub.values.sumOf { cnt -> cnt.toLong() * (cnt - 1) / 2 }
                parallelograms += totalPairs - sameSlope
            }
        }

        return (totalSegPairs - parallelograms).toInt()
    }

    private fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
    private fun abs(x: Int) = if (x < 0) -x else x
}

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