class Solution {
  fun specialTriplets(nums: IntArray): Int {
        val MOD = 1_000_000_007L
        val n = nums.size
        val maxVal = nums.maxOrNull() ?: 0
        val limit = maxVal * 2

        val rightCount = LongArray(limit + 1)
        val leftCount  = LongArray(limit + 1)
        for (v in nums) rightCount[v]++

        var result = 0L
        for (j in nums.indices) {
            val mid = nums[j]
            rightCount[mid]--

            val t = mid * 2
            if (t <= limit) {
                result = (result + leftCount[t] * rightCount[t]) % MOD
            }

            leftCount[mid]++
        }

        return result.toInt()
    }
}

class Solution {
    fun longestCommonPrefix(words: Array<String>): IntArray {
        val n = words.size
        val answer = IntArray(n)
        if (n <= 1) return answer

        val lcp = IntArray(n - 1)
        for (i in 0 until n - 1) {
            lcp[i] = commonPrefixLength(words[i], words[i + 1])
        }

        val prefixMax = IntArray(n - 1)
        prefixMax[0] = lcp[0]
        for (i in 1 until n - 1) {
            prefixMax[i] = maxOf(prefixMax[i - 1], lcp[i])
        }

        val suffixMax = IntArray(n - 1)
        suffixMax[n - 2] = lcp[n - 2]
        for (i in n - 3 downTo 0) {
            suffixMax[i] = maxOf(suffixMax[i + 1], lcp[i])
        }

        for (i in 0 until n) {
            var maxLen = 0
            if (i - 2 >= 0) {
                maxLen = maxOf(maxLen, prefixMax[i - 2])
            }
            if (i + 1 <= n - 2) {
                maxLen = maxOf(maxLen, suffixMax[i + 1])
            }
            if (i in 1 until n - 1) {
                val merged = commonPrefixLength(words[i - 1], words[i + 1])
                maxLen = maxOf(maxLen, merged)
            }
            answer[i] = maxLen
        }

        return answer
    }

    private fun commonPrefixLength(a: String, b: String): Int {
        val minLen = minOf(a.length, b.length)
        var i = 0
        while (i < minLen && a[i] == b[i]) {
            i++
        }
        return i
    }
}