Please note that since Ninjaclasher refused to write an editorial, wleung_bvg decided to write his own version. His solution is slightly different than intended.

Subtask 1

For the first subtask, we can see that for each pair of indices ~i~ and ~N-i+1~, there are only two options: swapped, and not swapped. Since there are ~\lfloor \frac N 2 \rfloor~ of these pairs (where ~i < N-i+1~), then there are ~2^{\lfloor \frac N 2 \rfloor}~ possible permutations of the books. For each permutation, we can count the minimum number of increasing and decreasing subsections using a greedy algorithm to extend the current subsection as long as possible in ~\mathcal{O}(N)~ time. We keep track of the minimum and print that as the answer.

Time Complexity: ~\mathcal{O}(N \cdot 2^{\lfloor \frac N 2 \rfloor})~

Subtask 2

This is a reminder that wleung_bvg still does not know how to dp, so please bear with him again.

For the second subtask, we can use dynamic programming to efficiently compute the answer. We will store the optimal answer for the subarrays ~[1, i]~ and ~[N-i+1, N]~ for all integers ~1 \le i \le \lceil \frac N 2 \rceil~. A key observation is that to compute the optimal answer, we only need to worry about the previous/next ~2~ elements in the array, in addition to the current element.

Let us define a function ~c(a, b, c)~. If ~b~ is either the maximum or minimum of ~\{a, b, c\}~, then ~c(a, b, c) = 1~. Otherwise, ~c(a, b, c) = 0~. If ~a, b, c~ are consecutive heights on the shelf, we can see that this corresponds to a change from either increasing to decreasing, or decreasing to increasing, which increases the instability of the shelf.

For simplicity, we can define another function ~f(i, inv)~. If ~inv = 1~, then ~f(i, inv) = h_{N-i+1}~, otherwise, ~f(i, inv) = h_i~.

Let ~dp[i][j][k][m]~ ~(1 \le i \le N~ and ~0 \le j, k, m \le 1)~ store the minimum instability for the subarray ~[1, i]~ and ~[N-i+1, N]~ where index ~i~ is swapped with ~N-i+1~ iff ~j = 1~, ~i-1~ is swapped with ~N-i~ iff ~k = 1~, and index ~i-2~ is swapped with ~N-i-1~ iff ~m = 1~.

We can see the optimal answer for each state relies on the optimal answer ending at index ~i-1~ with the same elements swapped as the current state. The optimal answer for the current state is at least ~\min(dp[i-1][k][m][0], dp[i-1][k][m][1])~.

We know that if there is a change in direction for ~f(i, j), f(i-1, k), f(i-2, m)~, then the optimal answer increases by one. This also applies for ~f(i, 1-j), f(i-1, 1-k), f(i-2, 1-m)~. Thus, we have the following:

$$\displaystyle \begin{align*} dp[i][j][k][m] =& \min(dp[i-1][k][m][0], dp[i-1][k][m][1]) \\ &+ c(f(i, j), f(i-1, k), f(i-2, m)) \\ &+ c(f(i, 1-j), f(i-1, 1-k), f(i-2, 1-m)) \end{align*}$$

When ~N~ is even, the optimal answer should be the minimum of ~dp[\frac N 2][j][k][m]~ for all ~0 \le j, k, m \le 1~, however the answer could possibly be off by ~1~ depending on the number of direction changes not counted between indices ~\frac N 2~ and ~\frac N 2 + 1~. Consider ~c(f(\frac N 2, j), f(\frac N 2 + 1, j), f(\frac N 2 + 2, k))~ and ~c(f(\frac N 2 - 1, j), f(\frac N 2, j), f(\frac N 2 + 1, k))~. If these two values are both ~0~, then it means that the subarray ~[\frac N 2 - 1, \frac N 2 + 2]~ belongs to the same subsection, and that ~dp[\frac N 2][j][k][m]~ is ~1~ greater than the actual answer. If both values are ~1~, then ~[\frac N 2, \frac N 2 + 1]~ forms an additional subsection that has not been counted and that ~dp[\frac N 2][j][k][m]~ is ~1~ less than the actual answer. In all other cases, ~dp[\frac N 2][j][k][m]~ stores the correct answer for those specific values of ~j, k, m~. We can keep track of the minimum for all ~0 \le j, k, m \le 1~ and print the answer.

It is very likely that one of the dimensions in the dynamic programming can be eliminated. Unfortunately wleung_bvg doesn't know how and since Ninjaclasher refused to write the editorial, this is what you get.

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

Subtask 3

For the third subtask, we can compute the ~dp~ array in the same way as subtask 2, however we have to handle the adjustment at the end differently. Consider ~c(f(\lceil \frac N 2 \rceil - 1, k), f(\lceil \frac N 2 \rceil, j), f(\lceil \frac N 2 \rceil + 1, k))~. If this value is ~0~, then ~[\lceil \frac N 2 \rceil - 1, \lceil \frac N 2 \rceil + 1]~ belongs to the same subsection, and ~dp[\lceil \frac N 2 \rceil][j][k][m]~ is ~1~ greater than the actual answer. Otherwise, the subsection formed by that change in direction has already been counted during the dynamic programming. Once again, the answer is the minimum of ~dp[\lceil \frac N 2 \rceil][j][k][m]~ for all ~0 \le j, k, m \le 1~.

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