class Solution {
    fun <A, B> product(
        xs: Sequence<A>,
        ys: Sequence<B>,
    ): Sequence<Pair<A, B>> = xs.flatMap { x -> ys.map { y -> x to y } }

    fun <A, B, C> product(
        xs: Sequence<A>,
        ys: Sequence<B>,
        zs: Sequence<C>,
    ): Sequence<Triple<A, B, C>> = xs.flatMap { x -> ys.flatMap { y -> zs.map { z -> Triple(x, y, z) } } }

    fun <A, B> product(
        xs: Iterable<A>,
        ys: Iterable<B>,
    ): Sequence<Pair<A, B>> = product(xs.asSequence(), ys.asSequence())

    fun <A, B, C> product(
        xs: Iterable<A>,
        ys: Iterable<B>,
        zs: Iterable<C>,
    ): Sequence<Triple<A, B, C>> = product(xs.asSequence(), ys.asSequence(), zs.asSequence())

    fun maxMoves(grid: Array<IntArray>): Int {
        val dp = Array(grid.size) { IntArray(grid[0].size) }

        product(grid[0].indices.reversed().drop(1), grid.indices, -1..1).filter {
                (x, y, dy) ->
            y + dy >= 0 && y + dy < dp.size && grid[y][x] < grid[y + dy][x + 1]
        }.forEach { (x, y, dy) ->
            dp[y][x] = listOf(dp[y][x], 1 + dp[y + dy][x + 1]).max()
        }

        return dp.indices.maxOf { y ->
            dp[y][0]
        }
    }
}