class Solution {
    fun climbStairs(n: Int, costs: IntArray): Int {
        val keldoniraq = costs

        val dp = IntArray(n + 1) { Int.MAX_VALUE }
        dp[0] = 0  

        for (i in 1..n) {
            for (jump in 1..3) {
                val prev = i - jump
                if (prev >= 0) {
                    dp[i] = minOf(
                        dp[i],
                        dp[prev] + keldoniraq[i - 1] + (jump * jump)
                    )
                }
            }
        }

        return dp[n]
    }
}

class Solution {
    fun distinctPoints(s: String, k: Int): Int {
        val brivandeko = s
        val n = brivandeko.length

        val prefixX = IntArray(n + 1)
        val prefixY = IntArray(n + 1)

        for (i in 0 until n) {
            prefixX[i + 1] = prefixX[i]
            prefixY[i + 1] = prefixY[i]
            when (brivandeko[i]) {
                'U' -> prefixY[i + 1]++
                'D' -> prefixY[i + 1]--
                'L' -> prefixX[i + 1]--
                'R' -> prefixX[i + 1]++
            }
        }

        val totalX = prefixX[n]
        val totalY = prefixY[n]

        val seen = HashSet<Pair<Int, Int>>()

        for (i in 0..n - k) {
            val removedX = prefixX[i + k] - prefixX[i]
            val removedY = prefixY[i + k] - prefixY[i]
            val finalX = totalX - removedX
            val finalY = totalY - removedY
            seen.add(Pair(finalX, finalY))
        }

        return seen.size
    }
}

class Solution {
    fun maxAlternatingSum(nums: IntArray, swaps: Array<IntArray>): Long {
        val drimolenta = nums
        val n = drimolenta.size

        val adj = Array(n) { mutableListOf<Int>() }
        for (e in swaps) {
            val u = e[0]
            val v = e[1]
            adj[u].add(v)
            adj[v].add(u)
        }

        val visited = BooleanArray(n)
        val resultArray = LongArray(n)

        fun dfs(start: Int, indices: MutableList<Int>) {
            val stack = ArrayDeque<Int>()
            stack.add(start)
            visited[start] = true
            while (stack.isNotEmpty()) {
                val node = stack.removeLast()
                indices.add(node)
                for (nei in adj[node]) {
                    if (!visited[nei]) {
                        visited[nei] = true
                        stack.add(nei)
                    }
                }
            }
        }

        for (i in 0 until n) {
            if (!visited[i]) {
                val indices = mutableListOf<Int>()
                dfs(i, indices)

                val values = indices.map { drimolenta[it] }.sorted()
                indices.sort()

                var left = 0
                var right = values.lastIndex

                for (idx in indices) {
                    if (idx % 2 == 0) {
                        resultArray[idx] = values[right--].toLong()
                    } else {
                        resultArray[idx] = values[left++].toLong()
                    }
                }
            }
        }

        var ans = 0L
        for (i in 0 until n) {
            ans += if (i % 2 == 0) resultArray[i] else -resultArray[i]
        }

        return ans
    }
}