Given an array A of positive integers (not necessarily distinct), return the lexicographically largest permutation that is smaller than A, that can be made with one swap (A swap exchanges the positions of two numbers A[i] and A[j]).  If it cannot be done, then return the same array.
 
Example 1:
Input: [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.

Example 2:
Input: [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.

Example 3:
Input: [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.

Example 4:
Input: [3,1,1,3]
Output: [1,3,1,3]
Explanation: Swapping 1 and 3.

 
Note:

1 <= A.length <= 10000
1 <= A[i] <= 10000

Difficulty: interview

Starter code:

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        

Solutions:
class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        n = len(A)
        if n == 1: return A
        
        tidx = -1
        for i in range(n-2, -1, -1):
            if A[i] > A[i+1]:
                tidx = i
                break
        
        if tidx < 0: return A
        
        sidx = -1
        for j in range(n-1, tidx, -1):
            if A[j] == A[j-1]: continue
            if A[j] < A[tidx]: 
                sidx = j
                break
        
        A[tidx], A[sidx] = A[sidx], A[tidx]
        
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        for i in range(len(A)-2, -1, -1):
            if A[i]>A[i+1]:
                break
        else:
            return A
        stack = []
        for j in range(i+1, len(A)):
            if A[j]<A[i]:
                while stack and A[stack[-1]]<A[j]:
                    stack.pop()
                stack.append(j)
        A[i], A[stack[0]] = A[stack[0]], A[i]
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        if len(A) == 1:
            return A

        for i in range(len(A) - 1, 0, -1):
            if A[i - 1] > A[i]:
                m, mi = A[i], i
                for j in range(i, len(A)):
                    if A[j] < A[i - 1] and A[j] > m:
                        mi = j
                        m = A[j]
                A[i - 1], A[mi] = A[mi], A[i - 1]
                break
        return A


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        n = len(A)
        for i in range(n - 2, -1, -1):
            if A[i] > A[i + 1]:
                pm = None
                for j in range(n - 1, i, -1):
                    if A[j] >= A[i]:
                        continue
                    if pm is None:
                        pm = j
                    elif A[j] == A[pm]:
                        pm = j
                    else:
                        break
                A[i], A[pm] = A[pm], A[i]
                return A
        return A


class Solution:
    
        
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        for i in range(len(A)-2,-1,-1):
            curr=-float(\"inf\")
            k=-1
            for j in range(i+1,len(A)):
                if A[j]>curr and A[j]<A[i]:
                    curr=A[j]
                    # print(curr,A[i],i,j)
                    k=j
            if curr!=-float(\"inf\"):
                # print(\"yo\")
                # print(k,j)
                A[i],A[k]=A[k],A[i]
                return A
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        max_index = -1
        for i in range(1, len(A)):
            if A[i - 1] > A[i]:
                max_index = max(max_index, i - 1)
        if max_index != -1:
            for i in range(max_index + 1, len(A)):
                if A[i] < A[max_index]:
                    j = i
            A[j], A[max_index] = A[max_index], A[j]
        return A
            


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        
        l = -1
        
        for i in reversed(range(len(A)-1)):
            if A[i] > A[i+1]:
                l = i
                break
                
        if l >= 0:
            r = l+1
            s = A[r]
            for i in range(l+2,len(A)):
                if A[i] < A[l] and A[i] >= s:
                    r = i
                    
            A[l],A[r] = A[r],A[l]
            
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        already_sorted = True
        swap_left = None
        for i in range(len(A)-1,0,-1):
            if A[i]<A[i-1]:
                swap_left = (i-1,A[i-1])
                already_sorted = False
                break
        if already_sorted: return A
        swap_right = None
        for i in range(swap_left[0]+1,len(A)):
            if A[i] < swap_left[1]:
                if swap_right and A[i]<=swap_right[1]:
                    continue
                else:
                    swap_right = (i, A[i])
        A[swap_right[0]],A[swap_left[0]] = swap_left[1], swap_right[1]
        return A
        
                    
        


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        if sorted(A) == A: return A
        
        n = len(A)
        s = A[:]
        for i in range(n-2, -1, -1):
            s[i] = min(s[i], s[i+1])
            if A[i] > s[i+1]:
                j = n-1
                while A[j] >= A[i]: j -= 1
                A[i], A[j] = A[j], A[i]
                return A


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        if len(A) == 1:
            return A
        
        prev = A[0]
        swapping = (0, -1)
        to_swap = (0, -1)
        for ind in range(1, len(A)):
            num = A[ind]
            if num < prev:
                swapping = (num, ind)
                to_swap = (A[ind - 1], ind - 1)
            elif num > swapping[0] and num < to_swap[0]:
                swapping = (num, ind)
                    
            prev = num
            
        if swapping[1] != -1:
            value = A[swapping[1]]
            A[swapping[1]] = A[to_swap[1]]
            A[to_swap[1]] = value
            
        return A


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        if A== []:
            return []
        last = float('inf')
        flag = False
        for i in range(len(A)-1, -1, -1):
            if A[i] > last:
                flag = True
                break
            last = A[i]
        if not flag:
            return A
        else:
            maxx = -float('inf')
            champ = None
            for j in range(i+1, len(A)):
                if A[j] > maxx and A[j] < A[i]:
                    champ = j
                    maxx = A[j]
            A[i], A[champ] = A[champ], A[i]
            
            return A


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        for i in range(len(A)-1, 0, -1):
            if A[i-1] > A[i]:
                break
        if i == 1 and A[i-1] <= A[i]:
            return A    
        j = max([x for x in range(i, len(A)) if A[x] < A[i-1]], key=lambda x:A[x])
        A[i-1], A[j] = A[j], A[i-1]
        return A
                
                


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        a_length = len(A)
        largest_left_index = 0
        largest_left = A[0]
        for i in range(2, a_length + 1):
            i *= -1
            if A[i] > A[i + 1]:
                largest_left_index = i
                largest_left = A[i]
                break

        largest_right_index = 0
        largest_right = 0
        for i in range(a_length + largest_left_index + 1, a_length):
            if A[i] > largest_right and A[i] < largest_left:
                largest_right_index = i
                largest_right = A[i]

        A[largest_left_index], A[largest_right_index] = A[largest_right_index], A[largest_left_index]
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        for i in range(len(A)-2, -1, -1):
            if A[i] > A[i+1]:
                break
        if A[i] <= A[i+1]:
            return A    
        j = max([x for x in range(i, len(A)) if A[x] < A[i]], key=lambda x:A[x])
        A[i], A[j] = A[j], A[i]
        return A
        # n=len(A)
        # for i in range(n-2,-1,-1):
        #     if A[i]<A[i+1]:
        #         minJ=-1
        #         for k in range(i+1,n):
        #             if A[k]>A[i]: minJ


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        stack = []
        for i in range(len(A)-1, -1, -1):
            if stack!=[] and stack[-1]<A[i]:
                break
            stack.append(A[i])
            
        if len(stack)==len(A):
            return A
        
        # print(i)
        stack = stack[::-1]
        low, high = 0, len(stack)-1
        while low<high-1:
            mid = (low+high)//2
            if stack[mid]>=A[i]:
                high = mid-1
            else:
                low = mid
        # print(stack[high])
        if stack[high]>=A[i]:
            high -= 1
        

        
        l = high-1
        while l>=0 and stack[l]==stack[high]:
            l -= 1
        l += 1
        # print(l)
        temp = A[i]
        A[i] = A[i+l+1]
        A[i+l+1] = temp
        
        return A


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        for i in range(len(A)-2, -1, -1):
            if A[i] > A[i+1]:
                break
        
        if A[i] <= A[i+1]:
            return A
        max_j = 0
        j_ind = i
        for j in range(i, len(A)):
            if A[i] > A[j]:
                max_j = max(max_j, A[j])
                if max_j == A[j]:
                    j_ind = j
        
        # swap
        tmp = A[i]
        A[i] = A[j_ind]
        A[j_ind] = tmp
        return A
        
        


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        \"\"\"
        res = -1
        for i in range(len(A)-1,0,-1):
        \"\"\"
        for i in range(len(A)-1,0,-1):
            if A[i] >= A[i-1]:
                continue
            else:
                val = A[i-1]
                j=-1
                while (A[j] >= val  or A[j] == A[j-1] ):
                    j-=1
            
            A[i-1], A[j] = A[j], A[i-1]
            break
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        n = len(A)
        if n == 1: return A
        
        tidx = -1
        for i in range(n-2, -1, -1):
            if A[i] > A[i+1]:
                tidx = i
                break
        
        if tidx < 0: return A
        
        target = A[tidx]
        sidx = -1
        for j in range(n-1, tidx, -1):
            if A[j] < target: 
                sidx = j
                break
        
        A[tidx], A[sidx] = A[sidx], A[tidx]
        
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        n = len(A)
        if n<=1: return A
        
        # moving left pointer
        left = n - 2
        while left >= 0 and A[left] <= A[left+1]:
            left -= 1
        if left < 0:
            return A
        
        # moving right pointer
        right = n-1
        while A[right] >= A[left]:
            right -= 1
        while A[right] == A[right-1]:
            right -= 1
            
        # swap left and right
        A[left],A[right] = A[right],A[left]
        
        return A


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        res = [val for val in A]
        length = len(A)
        start = 0
        haveInvertedPos = False
        # 寻找最后一个逆序位置
        for i in range(length-1):
            if A[i] <= A[i+1]:
                pass
            else:
                start = i
                haveInvertedPos = True
        # 没有逆序位置
        if not haveInvertedPos:
            return res
        target = start+1
        temp = A[target]
        for i in range(start+1, length):
            if A[i] < A[start] and A[i] > temp:
                temp = A[i]
                target = i
        # print(start, target)
        res[start], res[target] = res[target], res[start]
        return res


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        n = len(A)
        left = n - 1
        while left >= 1 and A[left-1] <= A[left]:
            left -= 1
        if left == 0:
            return A
        right = left
        left = left - 1
        for i in range(right, n):
            if A[i] > A[right] and A[i] < A[left]:
                right = i
        A[left], A[right] = A[right], A[left]
        return A


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        stack=[]
        find=-1
        for i in range(1,len(A)):
            if A[i]<A[i-1]:
                find=i-1
                break
        if find ==-1:
            return A
        j=find
        ind=[]
        3210
        while j<len(A):
            
            if len(stack)==0:
                stack.append(j)
                j+=1
                continue
            if A[j]<A[stack[-1]]:
                if len(stack)==2:
                    a=stack[-1]
                    stack=[a,j]
                else:
                    stack.append(j)
                j+=1
                continue
            else:
                if len(stack)==2:
                    ind=[stack[0],stack[1]]
                stack.pop()
        
        if len(stack)==2:
            A[stack[0]],A[stack[1]]=A[stack[1]],A[stack[0]]
            return A
        if len(ind)==2:
            A[ind[0]],A[ind[1]]=A[ind[1]],A[ind[0]]
            return A
        return A
        if len(stack)==0 and len(ind)==0:
            return A


class Solution:
  def prevPermOpt1(self, A: List[int]) -> List[int]:
    if not A:
      return A
    
    leftIndex = -1
    for i in range(len(A)-1, 0, -1):
      if A[i-1] > A[i]:
        leftIndex = i - 1
        break
    
    if leftIndex == -1:
      return A
  
    rightIndex = -1
    for i in range(len(A)-1, leftIndex, -1):
      if A[i] >= A[leftIndex]:
        continue
      elif rightIndex == -1:
        rightIndex = i
      elif A[i] == A[rightIndex]:
        rightIndex = i
    
    A[leftIndex], A[rightIndex] = A[rightIndex], A[leftIndex]
    return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        for i in range(len(A)-2, -1, -1):
            ans = (-1, -1)
            for j in range(i+1, len(A)):
                if A[j] < A[i]:
                    ans = max(ans, (A[j], -j)) # Find the maximum value, if value is the same we need the smallest j
            if ans[0] != -1:
                A[i], A[-ans[1]] = A[-ans[1]], A[i]
                return A
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        for i in range(len(A)-1, 0, -1):
            if A[i-1] > A[i]:
                break
        if A[i-1] <= A[i]:
            return A    
        j = max([x for x in range(i, len(A)) if A[x] < A[i-1]], key=lambda x:A[x])
        A[i-1], A[j] = A[j], A[i-1]
        return A
                
                


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        stack = [0]
        larger_index = [-1] * len(A)
        
        for i in range(1, len(A)):
            while stack and A[i] >= A[stack[-1]]:
                stack.pop()
            if stack:
                larger_index[i] = stack[-1]
            stack.append(i)
        
        print(larger_index)
        idx, swap = len(larger_index), -1
        for i in range(len(larger_index) - 1, -1, -1):
            if larger_index[i] == -1:
                continue
            if larger_index[i] > swap or (larger_index[i] == swap and A[i] >= A[idx]):
                val = A[larger_index[i]]
                idx = i
                swap = larger_index[i]
        if swap != -1:
            A[swap], A[idx] = A[idx], A[swap]
        return A
            
            


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        if len(A)<=1:
            return A
        left=len(A)-2
        while left>=0 and A[left]<=A[left+1]:
            left-=1
        
        if left<0:
            return A
        
        right=len(A)-1
        
        while A[right]>=A[left] and right>=0:
            right-=1
        
        while right>=0 and A[right]==A[right-1]:
            right-=1
            
        A[left],A[right]=A[right],A[left]
        return A
        
    


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        i=len(A)-2
        while(i>=0 and A[i]<=A[i+1]):
            i-=1
        if(i>=0):
            max_=i+1
            # max number greater on right that less than A[i]
            for j in range(max_+1,len(A)):
                if(A[max_]<A[j] and A[j]<A[i]):
                    max_=j
            A[max_],A[i]=A[i],A[max_]

        return A


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        mid = -1
        for i in range(len(A)-2,-1,-1):
            if A[i]>A[i+1]:
                mid = i
                break
        if mid ==-1:
            return A
        max_mid = -1
        for i in range(mid+1,len(A)):
            if A[mid]>A[i]:
                if A[i]>max_mid:
                    index = i
                    max_mid = A[i]
                #max_mid = max(max_mid,A[i])
        #index = A.index(max_mid)
        A[mid],A[index] = A[index],A[mid]
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        prev_vals = [(float('inf'), None)]
        
        for i in range(len(A) - 1, -1, -1):
            num = A[i]
            
            if num > prev_vals[-1][0]:
                max_prev = 0
                ind = None
                while num > prev_vals[-1][0]:
                    prev_n, prev_ind = prev_vals.pop()
                    if prev_n > max_prev:
                        max_prev = prev_n
                        ind = prev_ind
                
                A[i], A[ind] = max_prev, num
                return A
            
            prev_vals.append((num, i))
            
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        largest = len(A) - 2
        while largest >= 0 and A[largest] <= A[largest + 1]:
            largest -= 1
        if largest == -1:
            return A
        smallest = len(A) - 1
        while A[largest] <= A[smallest]:
            smallest -= 1
        f = smallest
        while A[smallest] == A[f]:
            f -= 1
        A[f + 1], A[largest] =  A[largest],A[f + 1]
        return A


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        idx = -1
        for i in range(len(A)-1):
            if A[i] > A[i+1]:
                idx = i
        
        if idx == -1:
            return A
        
        for i in range(len(A)-1, idx, -1):
            if A[i] < A[idx] and A[i] != A[i-1]:
                A[idx], A[i] = A[i], A[idx]
                break
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        for i in range(len(A)-2,-1,-1):
            for x in range(len(A)-1,i,-1):
                if A[x] == A[x-1]:
                    continue
                if A[i] > A[x]:
                    A[i],A[x] = A[x],A[i]
                    return A
        return A


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        n = len(A)
        if n<=1: return A
        
        # moving left pointer
        left = n-2
        while left>=0 and A[left]<=A[left+1]: 
            left -= 1
        if left < 0: return A
        
        # moving right pointer, skip same item
        right = n-1
        while A[right]>=A[left]: right -= 1
        while A[right]==A[right-1]: right -= 1
            
        # swap left and right
        A[left],A[right] = A[right],A[left]
        
        return A
        \"\"\"
        i1, n = -1, len(A)
        idx = n-2
        while idx >= 0:
            if A[idx] > A[idx+1]:
                i1 = idx
            else:
                idx -= 1
        
        if i1 == -1:
            return A
        
        # right #
        i2 = n-1
        while A[i2] >= A[i1]:
            i2 -= 1
        while A[i2] == A[i2-1]:
            i2 -= 1
        
        A[i1], A[i2] = A[i2], A[i1]
        return A
        
        
        i1 = -1
        idx = len(nums)-1
        while idx > 0:
            if nums[idx-1] > nums[idx]:
                i1 = idx-1
                break
            else:
                idx -= 1
        
        if i1 == -1:
            return nums
        
        for idx in reversed(range(i1+1, len(nums))):
            if nums[idx] < nums[i1] and nums[idx] != nums[idx-1]:
                nums[i1], nums[idx] = nums[idx], nums[i1]
         
        return nums
        \"\"\"

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        a_length = len(A)
        largest_left_index = 0
        largest_left = A[0]
        for i in range(2, a_length + 1):
            i *= -1
            if A[i] > A[i + 1]:
                largest_left_index = i
                largest_left = A[i]
                break
        
        largest_right_index = 0
        largest_right = 0
        for i in range(a_length + largest_left_index + 1, a_length):
            if A[i] > largest_right and A[i] < largest_left:
                largest_right_index = i
                largest_right = A[i]
        
        A[largest_left_index], A[largest_right_index] = A[largest_right_index], A[largest_left_index]
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        i = len(A) - 2
        
        while i >= 0 and A[i + 1] >= A[i]:
            i -= 1
        
        if i == -1:
            return A
        
        # find largest number just under A[i]
        k = i + 1
        j = i + 1
        while j < len(A):
            if A[k] < A[j] < A[i]:
                k = j
            j += 1
        A[i], A[k] = A[k], A[i]
        return A

        
        


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        point = -1
        for i in range(len(A) - 1, 0, -1):
            if A[i - 1] > A[i]:
                point = i - 1
                break
        if point == -1:
            return A
        right_point = point + 1
        max_val = -1
        for i in range(point + 1, len(A)):
            if A[i] < A[point] and max_val < A[i]:
                right_point = i
                max_val = A[i]
        A[point], A[right_point] = A[right_point], A[point]
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        
        for i in range(len(A)-2, -1, -1):
            if A[i] > A[i+1]:
                for j in range(i+1, len(A)):
                    if A[j] > A[i] or j==len(A)-1:
                        k = (j - 1) if A[j] > A[i] else j
                        while k > i and A[k] == A[i]:
                            k -= 1
                        while k - 1 > i and A[k-1]==A[k]:
                            k -= 1
                        A[i],A[k] = A[k],A[i]
                        break
                break
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        rear = len(A) - 2
        while rear > -1:
            if A[rear] > A[rear+1]:
                break
            rear -= 1
        if rear == -1:
            return A
        front = len(A) - 1
        while A[front] >= A[rear] or A[front-1] == A[front]:
            front -= 1
        A[rear], A[front] = A[front], A[rear]
        return A
            


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        if not A:
            return []
        
        i = len(A) - 1
        # find first elt A[i - 1] > A[i], from right to left
        # 1[9]467, find 9
        #   i
        while i > 0 and A[i - 1] <= A[i]:
            i -= 1
        if i == 0:
            return A # already at the smallest permutation
        
        # 1[9]46[7], find first elt < A[i - 1], which is 7
        # swap 9 and 7
        j = len(A) - 1
        while j > i and A[j] >= A[i - 1]:
            j -= 1
        
        
        while j >= i and A[j] == A[j - 1]:
            j -= 1
        
        A[j], A[i - 1] = A[i - 1], A[j]
        return A
        


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        l = len(A)-2
        while l >= 0:
            if A[l+1] < A[l]:
                break
            l -= 1
        max_so_far = 0
        max_idx = l
        r = l+1
        while r < len(A):
            if A[r] > max_so_far and A[r] < A[l]:
                max_so_far = A[r]
                max_idx = r
            r += 1
        if 0 <= l <= max_idx < len(A):
            A[l], A[max_idx] = A[max_idx], A[l]
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        
        # Start from the right, see if any values are smaller than current index
        
        smallestSeenSoFar = A[-1]
        
        swapOutIndex = -1
        for i in range(len(A) - 2, -1, -1):
            
            if A[i] > smallestSeenSoFar:
                # We can perform a swap on this index
                swapOutIndex = i
                break
            
            smallestSeenSoFar = min(smallestSeenSoFar, A[i])
        
        if swapOutIndex == -1:
            # We cannot swap out any values, so we terminate
            return A
        
        # Now, we need to find the largest index smaller than the swapout index
        swapInIndex = len(A) - 1
        largestSeenSmallerThanSwapout = 0
        
        for i in range(len(A) - 1, swapOutIndex, -1):
            
            if A[i] < A[swapOutIndex] and A[i] >= largestSeenSmallerThanSwapout:
                swapInIndex = i
                largestSeenSmallerThanSwapout = A[i]
                # We also choose the highest index that is matching our criterion
        
        # Now we found the swap in index, we perform the swap
        
        A[swapOutIndex], A[swapInIndex] = A[swapInIndex], A[swapOutIndex]
        
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        n = len(A)
        '''
        from end, find 1st number which is greater than atleast 1 no. from its right
        
        '''
        i,mn,mx = n-2,n-1,n-1
        while i >= 0:
            if A[i] > A[mn]: mx = i
            if A[i] < A[mn]: mn = i
            if mn != mx and mx < mn: break
            i-=1
        if i == -1: return A
        print((mx,mn))
        mxR = mx+1
        for j in range(mx+1,n):
            if A[j] < A[mx] and A[j] > A[mxR]: 
                mxR = j
        A[mx],A[mxR] = A[mxR],A[mx]
        return A
        


class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        '''
        5,6,1,1,1
        5,1,6,2,1
        '''
        for i in reversed(range(1,len(A))):
            if A[i-1] > A[i]:
                maxLessInd = i
                maxLessVal = A[i]
                for j in range(i+1,len(A)):
                    if A[j] > maxLessVal and A[j] < A[i-1]:
                        maxLessVal = A[j]
                        maxLessInd = j
                A[i-1], A[maxLessInd] =  A[maxLessInd], A[i-1]
                return A
        return A    

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        m = 10000
        idx = defaultdict(int)
        l = []

        for i in range(len(A)-1, -1, -1):
            if A[i]>m:
                l.sort()
                j = idx[l[bisect_left(l, A[i])-1]]
                A[i], A[j] = A[j], A[i]
                return A
            
            m = min(m, A[i])
            idx[A[i]] = i
            l.append(A[i])
        
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        if A == sorted(A): return A
        
        idx = None
        for i in range(len(A)-1,0, -1):
            if A[i-1] > A[i]:
                idx = i - 1
                break
        
        mx = float('-inf')
        for i in range(idx+1, len(A)):
            if mx < A[i] < A[idx]:
                mx = A[i]
                midx = i
        A[midx], A[idx] = A[idx], A[midx]
        return A

class Solution:
    def prevPermOpt1(self, A: List[int]) -> List[int]:
        def findLarger():
            prev = A[-1]
            for i in range(len(A)-1, -1, -1):
                if A[i] > prev:
                    return i
                prev = A[i]
            return -1
        if not A:
            return A
        larger = findLarger()
        if larger == -1:
            return A
        sl = larger + 1
        for i in range(larger, len(A)):
            if A[i] < A[larger]:
                if A[sl] < A[i]:
                    sl = i
        print((larger, sl))
        A[sl], A[larger] = A[larger], A[sl]
        return A