## Editorial for UHCC1 P3 - Busy Elevator

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: RAINY

For this problem, you are given an array of positive integers, , and a positive integer . You can change the position of at most one element in the array to maximize the such that .

Let be the initial maximum (i.e. without changing the position of any element, either ( and ) or ), and let be the index of the element you wish to change position, be the index of this element after changing its position, be the new array. Consider the following four situations:

Case 1: if , and , then as we just reordered the first elements, therefore this doesn't improve our answer.

Case 2: if , and , then it is optimal to pick the with maximum and move it to the back of the array.

Case 3: if , and , then it is optimal to pick the with minimum and move it to the front of the array.

Case 4: if , and , then moving any with to positions would have no effect on the answer, moving it to positions would reduce the problem to case 3. Now consider moving , as it potentially might be large and block the entrance to the elevator, so we move it to the back of the array.