If ~a_{i-1} \leq a_i \leq a_{i+1}~ or ~a_{i-1} \geq a_i \geq a_{i+1}~, performing an operation on ~i~ does nothing. If ~a_{i-1} > a_i < a_{i+1}~ then performing an operation on ~i~ will result in ~a_i = \min(a_{i-1}, a_{i+1})~. If ~a_{i-1} < a_i > a_{i+1}~ then performing an operation on ~i~ will result in ~a_i = \max(a_{i-1}, a_{i+1})~. After looking at these cases for a bit, we can observe that if ~a_i > a_{i+1}~ we can never have ~a_i < a_{i+1}~. Likewise, if ~a_i < a_{i+1}~, we can never have ~a_i > a_{i+1}~. We know that in order for ~a_i~ to decrease it must be greater than both of its neighbors, and for it to increase it must be less than both of its neighbors. Combining our previous observation with this, we can see that ~a_i~ can either only increase or only decrease. Therefore, ~a_i~ is either the minimum or maximum value of ~j~ where ~m_{i,j} = 1~.

Define ~l_i~ as the minimum value of ~j~ where ~m_{i,j} = 1~ and define ~r_i~ as the maximum value of ~j~ where ~m_{i,j} = 1~. If ~l_i = r_i~, we can obviously find ~a_i~. If ~l_i < a_{i-1}~, we know that ~a_i = l_i~. This is because if ~l_i = a_{i-1}~, we can't have ~a_i = l_i~ since we would have ~a_i = a_{i-1}~. If ~l_i > a_{i-1}~, we also can't have ~a_i = l_i~. The reason for this is that if we make ~a_i = l_i~, ~a_i~ must be an "increasing" index. In order for ~a_i~ to be increasing it must be less than both of its neighbors. However, in this case, ~a_i~ would be greater than ~a_{i-1}~. The only case we are left with is ~l_i \geq a_{i-1}~ which means that ~a_i = r_i~. Since we can easily find ~a_1~, we can loop through indices in increasing order and apply the above process to find ~a~.

Time Complexity: ~\mathcal{O}(N^2)~