Any sequence of towns fulfilling Mirko's condition can be constructed in the following way. Firstly, town 1 is added into the sequence. Then we add town 2 to the left or to the right of town 1. Then we add town 3 on the left or right end of the current sequence of towns. Next, town 4 is added on the left or the right end, and so on. Such sequence will fulfill Mirko's condition, and vice versa, any sequence fulfilling Mirko's condition can be constructed in the described manner.

Now the task can be solved using dynamic programming. The state is described with the left and right end of the current sequence. This is enough to tell us which town can be added next. Why? The town we added last is either on the left or right end, so its label is actually the maximum of those two numbers. The city being added next, of course, has a label increased by 1. We choose whether to put it on the left or right end: for each of those possibilities, we calculate the total flight duration as the duration of the chosen flight increased by the value of the next state in the dynamic. Moreover, we choose the more favorable solution as the current state value. The complexity of this algorithm is ~\mathcal O(N^2)~.