class Solution(object):

    def pancakeSort_dfs(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        res = []
        self.sort(A, set(), 0, res)

        return res

    def sort(self, A, memo, flips, res):
        if A == sorted(A):
            return True

        st = ''.join(map(str, A))
        memo.add(st)

        if flips >= 10 * len(A):
            return False

        for k in xrange(2, len(A) + 1):
            arr = A[:k][::-1] + A[k:]
            st = ''.join(map(str, arr))
            if st in memo:
                continue
            res.append(k)
            found = self.sort(arr, memo, flips + 1, res)
            if found:
                return True
            res.pop()

        return False

    def pancakeSort(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        B, res, N = sorted(A, reverse=True), [], len(A)

        for i in xrange(N):
            if B[i] != A[N - i - 1]:
                k = A.index(B[i]) + 1
                res.append(k)
                res.append(N - i)
                A = A[:k][::-1] + A[k:]
                A = A[:N - i][::-1] + A[N - i:]
        return res

    def pancakeSort2(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        res, N = [], len(A)

        for i in reversed(xrange(N)):
            if i + 1 != A[i]:
                k = A.index(i + 1) + 1
                res.append(k)
                res.append(i + 1)
                A = A[:k][::-1] + A[k:]
                A = A[:i + 1][::-1] + A[i + 1:]
        return res

    # TODO try to understand
    def pancakeSort3(self, A):
        ans = []

        N = len(A)
        B = sorted(range(1, N + 1), key=lambda i: -A[i - 1])
        for i in B:
            for f in ans:
                if i <= f:
                    i = f + 1 - i
            ans.extend([i, N])
            N -= 1

        return ans


if __name__ == '__main__':
    print Solution().pancakeSort([3, 2, 4, 1])
    print Solution().pancakeSort2([3, 2, 4, 1])
    print Solution().pancakeSort3([3, 2, 4, 1])
    print Solution().pancakeSort([10, 5, 1, 6, 3, 8, 2, 4, 7, 9])
    print Solution().pancakeSort2([10, 5, 1, 6, 3, 8, 2, 4, 7, 9])
    print Solution().pancakeSort3([10, 5, 1, 6, 3, 8, 2, 4, 7, 9])
