If there is \(i\) such that \(A_i > A_{i+1}\), let \(k\) be the leftmost such index.

Let \(j\) be the smallest \(i\) among the \(i\)’s such that \(A_k=A_i\). Then, \(A\) begins with \(A_1 \leq A_2 \leq \cdots \leq A_{j-1} < A_j = A_{j+1} = \cdots = A_k > A_{k+1}\). If we choose \(x=A_k\) here, \(a\) will begin with \(A_1, A_2, \cdots, A_{j-1}, A_{k+1}\), which can be verified to be lexicographically smaller than \(A\). (They share the first \(j-1\) elements, and the \(j\)-th element of \(a\) is smaller than that of \(A\).)

If we choose a different value for \(x\), an argument similar to above shows that the result will not be better than when \(x=A_k\).

Thus, \(x=A_k\) is an optimal choice.

If there is no \(i\) such that \(A_i > A_{i+1}\), the optimal choice is \(x=A_N\) since \(A\) is non-decreasing.

Implementation of the above will run in \(O(N)\) time.

Sample Solution (pypy3)