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
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]:
    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