#
#
#
# class Solution(object):Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j].
# The width of such a ramp is j - i.
#
# Find the maximum width of a ramp in A.  If one doesn't exist, return 0.
#
#
#
# Example 1:
#
# Input: [6,0,8,2,1,5]
# Output: 4
# Explanation:
# The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.
# Example 2:
#
# Input: [9,8,1,0,1,9,4,0,4,1]
# Output: 7
# Explanation:
# The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.
#
#
# Note:
#
# 2 <= A.length <= 50000
# 0 <= A[i] <= 50000
import bisect


class BIT(object):
    def __init__(self, n):
        # bit starts from index 1
        self.__bits = [0] * n
        self.__n = n

    def _lowBit(self, x):
        return x & -x

    # beware, in this problem, `update` is using '-' lowBit
    # regluar one would use `+`
    def update(self, i, val):
        # review i need to start from 1 instead of 0
        i += 1
        while i:
            self.__bits[i] = max(self.__bits[i], val)
            i -= self._lowBit(i)

    def query(self, idx):
        # notice we use idx + 1
        res, idx = 0, idx + 1
        while idx <= self.__n:
            res = max(res, self.__bits[idx])
            idx += self._lowBit(idx)
        return res






class Solution(object):
    def maxWidthRamp_tle(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        n = len(A)
        dp = [0] * n

        for i in xrange(1, n):
            for j in xrange(i - 1, -1, -1):
                if A[i] >= A[j]:
                    dp[j] = i - j

        return max(dp)

    def maxWidthRamp_tlei2(self, A):
        """
        :type A: List[int]
        :rtype: int
        """

        ends, res = {c: i for i, c in enumerate(A)}, 0

        for k, v in enumerate(A):
            t = max([ends[m] for m in ends.keys() if m >= v])
            res = max(res, t - k)
        return res

    def maxWidthRamp(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        n = len(A)
        left, right = [0] * n, [0] * n
        left[0], right[n - 1] = A[0], A[-1]

        for k, v in enumerate(A):
            if k > 0:
                left[k] = min(left[k - 1], v)
                right[n - k - 1] = max(right[n - k], A[n - k - 1])

        i, j, res = 0, 0, 0
        while i < n and j < n:
            if left[i] <= right[j]:
                res = max(res, j - i)
                j += 1
            else:
                i += 1

        return res

    def maxWidthRamp2(self, A):
        """
        :type A: List[int]
        :rtype: int
        """

        idx = range(len(A))

        lmin, res = float('inf'), 0
        for k in sorted(idx, cmp=lambda i, j: A[i] - A[j]):
            lmin = min(idx[k], lmin)
            res = max(res, idx[k] - lmin)
        return res

    def maxWidthRamp3(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        idx = range(len(A))

        lmin, res = float('inf'), 0
        for k in sorted(idx, key=A.__getitem__):
            lmin = min(idx[k], lmin)
            res = max(res, idx[k] - lmin)
        return res

    # using binary indexed tree
    def maxWidthRamp4(self, A):
        """
        :type A: List[int]
        :rtype: int
        """

        bitree, res = BIT(50010), -1

        for i in xrange(len(A) - 1, -1, -1):
            res = max(res, bitree.query(A[i]) - i)
            bitree.update(A[i], i)

        return res

    # using stack
    def maxWidthRamp6(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        st, res = [], -1

        for k, v in enumerate(A):
            if not st or A[st[-1]] >= v:
                st.append(k)

        for k in reversed(xrange(len(A))):
            # bugfixed, should be >= instead fo >
            while st and A[k] >= A[st[-1]]:
                res = max(res, k - st.pop())

        return res

    # binary search
    def maxWidthRamp5(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        N = len(A)
        candidates, res = [(A[-1], N - 1)], -1

        for i in xrange(N - 2, -1, -1):
            ins = bisect.bisect(candidates, (A[i],))
            if ins < len(candidates):
                res = max(res, candidates[ins][1] - i)
            else:
                candidates.append((A[i], i))

        return res





if __name__ == '__main__':
    # print Solution().maxWidthRamp([6, 0, 8, 2, 1, 5])
    print Solution().maxWidthRamp([3, 2, 4, 1])
    print Solution().maxWidthRamp2([3, 2, 4, 1])
    print Solution().maxWidthRamp3([3, 2, 4, 1])
    print Solution().maxWidthRamp4([3, 2, 4, 1])
    print Solution().maxWidthRamp5([3, 2, 4, 1])
    print Solution().maxWidthRamp6([3, 2, 4, 1])
    print Solution().maxWidthRamp([9, 8, 1, 0, 1, 9, 4, 0, 4, 1])
    print Solution().maxWidthRamp2([9, 8, 1, 0, 1, 9, 4, 0, 4, 1])
    print Solution().maxWidthRamp3([9, 8, 1, 0, 1, 9, 4, 0, 4, 1])
    print Solution().maxWidthRamp4([9, 8, 1, 0, 1, 9, 4, 0, 4, 1])
    print Solution().maxWidthRamp5([9, 8, 1, 0, 1, 9, 4, 0, 4, 1])
    print Solution().maxWidthRamp6([9, 8, 1, 0, 1, 9, 4, 0, 4, 1])
