1
# Runtime: 486 ms (Top 14.08%) | Memory: 15.3 MB (Top 47.61%)
2
class Solution:
3

4
    def find_max(self, i, a, n):
5
        maxs = i + 1
6
        for j in range(n - 1, i, -1):
7
            # if only j is greater than max and smaller than first descending element
8
            if a[maxs] <= a[j] and a[j] < a[i]:
9
                maxs = j
10
        # Swap
11
        a[i], a[maxs] = a[maxs], a[i]
12
        return a
13

14
    def prevPermOpt1(self, arr):
15
        n = len(arr)
16
        for i in range(n - 1, 0, -1):
17
            if arr[i] < arr[i - 1]:
18
                # sending the first descending element from right to max_function
19
                arr = self.find_max(i - 1, arr, n)
20
                break
21
        return arr