[Question]
  [
## Introduction
Suppose you want to compute the tail maxima of a list of numbers, that is, the maximum of each nonempty suffix.
One way to do it is to repeatedly choose one number and replace it by a higher number occurring after it, until this is not possible anymore.
In this challenge, your task is to perform one step of this algorithm.
## The task
Your input is a list of integers **L**, which may be empty.
Your output shall be the list **L** where exactly one number **Li** has been replaced by another **Lj**, where **Li < Lj** and **i < j**.
In other words, you shall replace one number with a higher number that occurs after it.
You can choose **i** and **j** freely among all valid pairs, and the choice can be nondeterministic.
If such **i** and **j** do not exist (i.e. **L** is non-increasing), your output shall be **L** unchanged.
## Example
Consider the input **L = [ 3, 1, 4, -1, 2 ]**.
The possible operations are to replace **3** by **4**, replace **1** by **4**, replace **1** by **2**, or replace **-1** by **2**.
Thus the possible outputs are:
```
 [  3 ,   1 ,   4 ,  -1 ,   2 ]
 ------------------------------
 [( 4),   1 ,(  4),  -1 ,   2 ]
 [  3 ,(  4),(  4),  -1 ,   2 ]
 [  3 ,(  2),   4 ,  -1 ,(  2)]
 [  3 ,   1 ,   4 ,(  2),(  2)]
```
If you repeat the operation enough times, the end result will be **[4,4,4,2,2]**, which is precisely the list of tail maxima of **L**.
## Rules and scoring
You can write a full program or a function.
In the latter case, you can modify the input in place instead of returning a new array, if your language allows that.
Input and output formats are flexible within reason.
The lowest byte count wins.
## Test cases
All possible outputs are shown.
```
[] -> []
[1] -> [1]
[1,2] -> [2,2]
[2,1] -> [2,1]
[4,4,4,4] -> [4,4,4,4]
[-1,-3,-10] -> [-1,-3,-10]
[1,3,10] -> [3,3,10] [10,3,10] [1,10,10]
[1,1,2,1] -> [2,1,2,1] [1,2,2,1]
[998,64,2,-94,-789] -> [998,64,2,-94,-789]
[998,2,64,-94,-789] -> [998,64,64,-94,-789]
[3,1,4,-1,2] -> [4,1,4,-1,2] [3,4,4,-1,2] [3,2,4,-1,2] [3,1,4,2,2]
[-1,4,0,4,7,2,3] -> [4,4,0,4,7,2,3] [0,4,0,4,7,2,3] [-1,4,4,4,7,2,3] [7,4,0,4,7,2,3] [-1,7,0,4,7,2,3] [-1,4,7,4,7,2,3] [-1,4,0,7,7,2,3] [2,4,0,4,7,2,3] [-1,4,2,4,7,2,3] [3,4,0,4,7,2,3] [-1,4,3,4,7,2,3] [-1,4,0,4,7,3,3]
[3542,-12311,7662,1672,6081] -> [7662,-12311,7662,1672,6081] [3542,7662,7662,1672,6081] [3542,1672,7662,1672,6081] [6081,-12311,7662,1672,6081] [3542,6081,7662,1672,6081] [3542,-12311,7662,6081,6081]
```
  
[Answer]
# JavaScript (ES6), ~~41~~ ~~40~~ ~~39~~ 38 bytes
*Saved a byte thanks to @Neil, another thanks to @user81655*
```
x=>x.map(c=>c<x[++i]>d?x[d=i]:c,d=i=0)
```
Just when it seems `reduceRight` might finally have a chance, `.map` shows up yet again...
[Answer]
# Mathematica, 37 bytes
```
#/.{a___,b_,c_,d___}/;b<c:>{a,c,c,d}&
```
Pure function taking a list of real numbers even, and returning a list of real numbers. Looks for the first pair of consecutive entries in the "wrong" order, and replaces the first of that pair with the second. Nice default behavior of `/.` means that it returns the input unaltered when appropriate.
Amusing side note: if we replace `b<c` with `!OrderedQ[{c,b}]`, then the function works on strings (and really any data type once the appropriate ordering is described). For example, `#/.{a___,b_,c_,d___}/;!OrderedQ[{c,b}]:>{a,c,c,d}&` on input `{"programming", "puzzles", "code", "golf"}` returns `{"puzzles", "puzzles", "code", "golf"}`.
[Answer]
## JavaScript (ES6), ~~43~~ ~~39~~ 38 bytes
```
a=>a[a.some(e=>e<a[++i],i=0)*i-1]=a[i]
```
Outputs by modifying the array in-place. Edit: Saved 4 bytes thanks to @ETHproductions. Saved 1 byte thanks to @user81655.
[Answer]
# [Haskell](https://www.haskell.org/), 36 bytes
```
f(a:r@(b:_))|a<b=b:r|1>0=a:f r
f e=e
```
[Try it online!](https://tio.run/nexus/haskell#PU5BCsMgELznFXuMsAsxCW2UWPqBvkCkKCjkkBBMjv49USll2ZndYRjmCq2V8d06@WUs2dkpJ2Pir05ZGSA2Abzy1@mP81BaG9S8LPYVM2P@QY9YJ4vEkQYk3lXDgPUQYsLHmM0kRqTnJH5aX9S/BqizP@dQyTfNapcNFKx2/8Ael@0E3ZYiGKAQSwVnqt3MdQM "Haskell – TIO Nexus")
Look through the list for consecutive elements `a,b` with `a<b` and changes them to `b,b`.
Improved from 37 bytes:
```
f(a:b:t)|a<b=b:b:t
f(a:t)=a:f t
f e=e
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~13~~ 11 bytes
```
ṫJṀ€ż¹ŒpQ-ị
```
Replaces the rightmost of all possible numbers.
[Try it online!](https://tio.run/nexus/jelly#@/9w52qvhzsbHjWtObrn0M6jkwoCdR/u7v5/uB0o4v7/f3SsjkK0IZjQMQJRRjpgnokOGIKYuoY6usY6uoYGEFXGOjAWUAdEsaWlhY6ZCZCna2mio2tuYQkTNAIJIwsCNQON1YXapQviGACxOVClMVje1ARoiqGRsaGhjrmZGdB8M3OgIQYWhrEA "Jelly – TIO Nexus")
### How it works
```
ṫJṀ€ż¹ŒpQ-ị  Main link. Argument: A (array)
 J           Yield all indices of A, i.e., the array [1, ..., len(A)].
ṫ            Dyadic tail; for index k, take all elements starting with the k-th.
             This constructs the array of suffixes.
  Ṁ€         Maximum each; map the monadic maximum atom over the suffixes.
     ¹       Identity; yield A.
    ż        Zip; construct all pairs of elements of the result to the left and the
             corresponding elements of the result to the right.
      Œp     Cartesian product. Construct all arrays that, for each index, take
             either the left or the right element.
        Q    Unique; deduplicate the resulting arrays.
         -ị  At-index -1; select the second to last result.
             The last result is A itself, the first maxima of suffixes.
```
[Answer]
# [MATL](https://github.com/lmendo/MATL), 15 bytes
```
tdt0>0whY>d*0h+
```
[Try it online!](https://tio.run/nexus/matl#@1@SUmJgZ1CeEWmXomWQof3/f7SxjqGOiY6uoY5RLAA "MATL – TIO Nexus")
I'm not a huge fan of this solution. It seems horribly inefficient to me. Particularly the `whY>d*` and `0h+` sections.
[Answer]
# Python 2, ~~139~~ ~~134~~ 93 bytes
```
a=input()
for i in range(len(a)):
 for j in a[i+1:]:
    if a[i]<j:a[i]=j;print a;exit()
print a
```
Terribly long, but it's a first attempt.
-5 bytes thanks to TemporalWolf  
-41 (!!) bytes thanks to Value Ink 
[Answer]
# [MATL](https://github.com/lmendo/MATL), 13 bytes
```
ttd0>fX>Q)2M(
```
[Try it online!](https://tio.run/nexus/matl#@19SkmJglxZhF6hp5Kvx/3@0samJkY6uoZGxoaGOuZmZkY6hmbmRjpmBhWEsAA "MATL – TIO Nexus")
### Explanation
The following two conditions are equivalent:
1. There is a number that has a higher number to its right
2. There is a number that has a higher number immediately to its right
The code uses condition 2, which is simpler. It computes consecutive increments and finds the last positive one, if any. For the two involved entries, it writes the value of the second entry into the first.
[This trick](https://codegolf.stackexchange.com/a/79189/36398) is used to handle the case when no substitution can be done. Note also that MATL indexing is `1`-based.
Let's use input `[3,1,4,-1,2]` as an example.
```
tt    % Get input implicitly and duplicate it twice
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [3,1,4,-1,2]
d     % Consecutive differences
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [-2  3 -5  3]
0>    % Are they positive?
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [0 1 0 1]
f     % Find indices of all positive differences. Result may be empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], [2 4]
X>    % Maximum index with a positive difference. Empty input remains as empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], 4
Q     % Add 1. Since the addition is elementwise, empty input remains as empty
      % STACK: [3,1,4,-1,2], [3,1,4,-1,2], 5
)     % Get the entry of the input at that position
      % STACK: [3,1,4,-1,2], 2
2M    % Push maximum index with a positive difference, again
      % STACK: [3,1,4,-1,2], 2, 4
(     % Assign to that position. Implicitly display
      % STACK: [3,1,4,2,2]
```
[Answer]
# [Haskell](https://www.haskell.org/), ~~34~~ 33 bytes
This is based on [the answer by xnor](https://codegolf.stackexchange.com/a/113835/), who suggested I post it myself. 
EDIT: xnor found a byte to save.
```
f(a:r@(b:_))=max(b:r)$a:f r
f e=e
```
[Try it online!](https://tio.run/nexus/haskell#PU5BCsMwDLv3FT7skIANaxu2JiywD@wFoYwMEuihpaQ97LC/d3YYw1iShTA6soqu3NXLPbX2c3yzKvoUXYbSZEg@HXva9s2HMGJoZbGryIx8QzBYh01qkXqk9lwDPVZh7YAXw2GyBuk62J/Xifv3AAPn@Q/J/7GZ47SAhzmuD1jLtOwQlBTBDEL6I3ij2m08vg "Haskell – TIO Nexus")
Basically, I observed that the branching of xnor's method always ends up choosing whichever of the branch expressions is largest, since Haskell uses lexicographic ordering for lists. (The case when `a==b` also works because `f r>=r`, which can be proved separately by induction.)
Put differently, whenever `b:r > a:f r`, then `b:r` is a correct answer, and otherwise we can recurse to `a:f r`.
So instead of checking `a<b` in advance, I just calculate both expressions and take the maximum. This could give an exponential blowup, although Haskell's laziness avoids that unless `a` and `b` are equal.
[Answer]
# Python 3, 79 bytes
```
def f(x):
 for i,a in enumerate(x):
  m=max(x[i+1:])
  if m>a:x[i]=m;break
```
Mutates the original array (list) given to it. I'm unhappy that this isn't a lambda and I'm sure there are better optimizations; I'll hopefully address those later.
### Brief explanation
It takes the max of the array past the current element (starting with the zeroth). It then compares this to the element itself: if the max is greater, replace the current element with it and stop, otherwise, increment by one and keep trying that.
[Answer]
# Ruby, ~~66~~ 61 bytes
```
->a{i=r=-1;a.map{|e|m=a[i+=1,a.size].max;r&&m>e ?(r=!r;m):e}}
```
[Try it online!](https://tio.run/nexus/ruby#bY5BCoMwEEX3nsJupKUz4sQ0mkrsQcRFKAqCAbGbUvXsduzKSAmBzPvJy19bg6WdOjMapMLGzg7T3MzO2Kq7GgIbv7pPUzN/F2MUubIJH@fRnMbCXe7NsgTBELbx0/Z9WNW7M3kDiP0owEsl/NYeIQGmgJT4lhSOhM2@TOsclGSKWgJmuT6GYov/hSznGnjoihtMeGf8MvXu3yT/QiIlgkwp7qEylic51ev6BQ "Ruby – TIO Nexus")
[Answer]
# C, 47 bytes
```
f(p,n)int*p;{n>1?*p<p[1]?*p=p[1]:f(p+1,n-1):0;}
```
Recursive implementation taking as its input a pointer to the first element of an array, and the length of the array. Modifies the array in place.
[Answer]
## SWI-Prolog, 70 bytes
```
f([H|T],[S|T]):-max_list(T,S),S>H,!.
f([H|T],[H|R]):-f(T,R),!.
f(I,I).
```
First clause replaces the first element of the list with the maximum value of the rest of the list, but only if this max is bigger. The second clause recursively calls the predicate for the tail of the list. If none of these clauses succeed, the third clause simply returns the input.
This return just one of the possible solutions. It's trivial to find all of them with very similar code, but then the case where no change is possible takes a lot more bytes to handle.
Example:
```
?- f([-1,4,0,4,7,2,3], O).
O = [7, 4, 0, 4, 7, 2, 3]
```
[Answer]
## R, 71 bytes
```
a=scan()
l=length(a) 
lapply(1:l,function(x){
  a[x]=max(a[x:l])
  a
})
```
[Answer]
# C, 80 bytes
```
i,j;f(l,n)int*l;{for(i=0;i<n;++i)for(j=i;++j<n;)if(l[i]<l[j]){l[i]=l[j];j=i=n;}}
```
Call with:
```
int main()
{
    int a[5]={3,1,4,-1,2};
    f(a,5);
    for(int k=0;k<5;++k)
        printf("%d ", a[k]);
}
```
[Answer]
## Python 2, 89 bytes
[Try it online](https://tio.run/nexus/python2#@5@SmqbgpuGoacWlkJZfpJCpkJmnUJSYl56qkZOaBxQHSnAW2UZXgmUrQbKO0ZnahlaxmWkKlXZAdmwsFyeQXWQFYtsWRRvEWicVpSZm/3e0jTY00DHRAWFzHSMd41gukEVcBUWZeSUKjv8B) 
-1 byte thanks to @TemporalWolf  
-25 bytes thanks to @ValueInk  
-7 bytes thanks to @Cole 
Function that mutates input array 
```
def F(A):
 for i in range(len(A)):
    r=[y for y in A[i+1:]if y>A[i]]
    if r:A[i]=r[0];break
```
If there was no need to stop after first iteration, it would be a bit prettier 
[Answer]
# Python 2, 60 bytes
```
f=lambda x:x and[x[:1]+f(x[1:]),[max(x)]+x[1:]][x[0]<max(x)]
```
[Try it Online!](https://tio.run/nexus/python2#TcvBCoMwDADQu1@Ro2IEU7valu1LQg4dUihMN2SH/r2rxcMICclLcsTHK6zPJUD2GcK2cGZP0sc2M3npkNeQ29xJX2cp61Hulx3xvUOCtAGzINOZqEpVePYaa1QtXs05i0aXYXAah9m6y9SpfzbddLkhNRHhbEx5NnO5GS2J@AY@e9q@ENvUNccP)
**Explanation:** Recursively checks if a given element is less than the `max` element in the rest of the list. If so, returns the list with `max` replacing the first element.
[Answer]
# TI-Basic, 72 bytes
```
Prompt L1
If 2≤dim(L1
Then
For(A,1,dim(L1)-1
For(B,A,dim(L1
If L1(A)<L1(B
Then
L1(B→L1(A
Goto E
End
End
End
End
Lbl E
L1
```
Explanation:
```
Prompt L1          # 4 bytes, input list
If 2≤dim(L1        # 7 bytes, if the list has 2 or 1 element(s), skip this part and return it
Then               # 2 bytes
For(A,1,dim(L1)-1  # 12 bytes, for each element in the list other than the last
For(B,A,dim(L1     # 9 bytes, for each element after that one
If L1(A)<L1(B      # 12 bytes, if the second is larger than the first
Then               # 2 bytes
L1(B→L1(A          # 10 bytes, replace the first with the second
Goto E             # 3 bytes, and exit
End                # 2 bytes
End                # 2 bytes
End                # 2 bytes
End                # 2 bytes
Lbl E              # 3 bytes
L1                 # 2 bytes, implicitly return L1
```
[Answer]
# sh, 118 bytes
Input integers are passed as arguments to the script.
```
l=("$@");for i in "$@";{ for j in "$@";{(($i<$j))&&{ l[$x]=$j;echo ${l[@]};exit;};};shift;x=`expr $x+1`;};echo ${l[@]}
```
Breakdown:
```
l=("$@");                      #copy original list
for i in "$@";{ for j in "$@"; #check all elements j that follow element i in list
{(($i<$j))&&{ l[$x]=$j;echo ${l[@]};exit;};};   #if i<j, make i=j; print list, done
shift;                         #makes sure that i is compared only to j that occur after it
x=`expr $x+1`;};               #keeps track of i'th position in the list
echo ${l[@]}                   #prints list if it was unchanged
```
[Answer]
# PHP, 88 Bytes
```
<?for(;$i+1<$c=count($a=$_GET)&&$a[+$i]>=$a[++$i];);$i>=$c?:$a[$i-1]=$a[$i];print_r($a);
```
## Breakdown
```
for(;
$i+1<($c=count($a=$_GET))  # first condition end loop if the item before the last is reach 
&&$a[+$i]>=$a[++$i] # second condition end loop if item is greater then before 
;);
$i>=$c?:$a[$i-1]=$a[$i]; # replace if a greater item is found
print_r($a); #Output
```
[Answer]
## Haskell, 48 bytes
```
f(b:l)|l>[],m<-maximum l,b<m=m:l|1<2=b:f l
f x=x
```
Usage example: `f [1,1,2,1]` -> `[2,1,2,1]`. [Try it online!](https://tio.run/nexus/haskell#@5@mkWSVo1mTYxcdq5Nro5ubWJGZW5qrkKOTZJNrm2uVU2NoY2SbZJWmkMOVplBhW/E/NzEzT8FWoaAoM69EQUUhTSHaUMdQx0jHMPY/AA "Haskell – TIO Nexus").
If the input list has at least one element, bind `b` to the first element and `l` to the rest of the list. If `l` is not empty and `b` less than the maximum of `l`, return the maximum followed by `l`, else return `b` followed by a recursive call of `f l`. If the input list is empty, return it. 
[Answer]
## Racket 202 bytes
```
(let((g(λ(L i n)(for/list((c(in-naturals))(l L))(if(= c i)n l))))(ol'()))
(for((c(in-naturals))(i L))(for((d(in-range c(length L)))#:when(>(list-ref L d)i))
(set! ol(cons(g L c(list-ref L d))ol))))ol)
```
Ungolfed: 
```
(define (f L)
  (let ((replace (λ (L i n)   ; sub-function to replace i-th item in list L with n;
                   (for/list ((c (in-naturals))
                              (l L))
                     (if (= c i) n l))))
        (ol '()))             ; outlist initially empty; 
    (for ((c (in-naturals))               ; for each item in list
          (i L))
      (for ((d (in-range c (length L)))   ; check each subsequent item in list
            #:when (> (list-ref L d) i))  ; if greater, replace it in list
        (set! ol (cons (replace L c (list-ref L d)) ol)))) ; and add to outlist.
    ol))          ; return outlist.
```
Testing: 
```
(f '(3 1 4 -1 2))
```
Output: 
```
'((3 1 4 2 2) (3 2 4 -1 2) (3 4 4 -1 2) (4 1 4 -1 2))
```
[Answer]
# C, 67 bytes
**Single Run, 67 bytes** [Live](http://ideone.com/fe8XI4)
```
j;f(l,i)int*l;{j=i-1;while(i-->0)while(j-->0)l[j]=fmax(l[i],l[j]);}
```
**Single Step, 78 bytes** [Live](http://ideone.com/xp8tpi)
```
j;f(l,i)int*l;{j=i-1;while(i-->0)while(j-->0)if(l[j]<l[i]){l[j]=l[i];return;}}
```
**Tail Maxima, 96 bytes** [Live](http://ideone.com/JeDMAp)
```
x;i;j;f(l,n)int*l;{do{x=0;for(i=0;i<n;i++)for(j=0;j<i;j++)if(l[j]<l[i])l[j]=l[i],x=1;}while(x);}
```
[Answer]
# [Python 3](https://docs.python.org/3/), ~~103~~ 102 bytes
```
lambda a:([a[:i]+[max(a[i:])]+a[i+1:]for i in range(len(a))if-~i==len(a)or max(a[i+1:])>a[i]]+[[]])[0]
```
[Try it online!](https://tio.run/##PU7bDsIgDH33K4hPkBXjLlFHsv0I9qHGTUkcmo0HjdFfnwWNEOjp6elpb49wvvpy7pv9fKHhcCRBRlqyxmFmB7pLss6gwoxjlhvsr6Nwwnkxkj918tJ5SUq5Xr9d03wzVvwaY4NqGSCbWURl1ziHbgpTwynYPD4o@K8gXUY6B12CztepVkICdb2DTQUF6LoCvd3VP66I7J8TYFnPPjqa4iLuGqfFddNUsxB8bqPzQS6fL6Fb8XwtV6wbKMgogT4FpdT8AQ "Python 3 – Try It Online")
]