class Solution {
    private fun min(
        x: Int,
        y: Int,
    ): Int = listOf(x, y).min()

    private fun max(
        x: Int,
        y: Int,
    ): Int = listOf(x, y).max()

    private data class State(
        val prevMax: Int,
        val bitCount: Int,
        val min: Int,
        val max: Int,
    ) {
        val sortable: Boolean
            get() = min >= prevMax

        private fun getSegmentMaximum(
            prevMax: Int,
            min: Int,
            max: Int,
        ): Int =
            if (min < prevMax) {
                Int.MAX_VALUE
            } else {
                max
            }

        fun update(num: Int): State =
            if (bitCount == num.countOneBits()) {
                State(prevMax, bitCount, min(min, num), max(max, num))
            } else {
                State(getSegmentMaximum(prevMax, min, max), num.countOneBits(), num, num)
            }
    }

    private fun getInitialState(num: Int): State = State(Int.MIN_VALUE, num.countOneBits(), num, num)

    fun canSortArray(nums: IntArray): Boolean =
        nums.fold(getInitialState(nums[0])) { acc, it ->
            acc.update(it)
        }.sortable
}