An initial observation is that the final happiness of a resident depends only on whether the resident's final position differs from their initial position by an odd or an even displacement. Therefore, the only important information to describe a state is a permutation representing where the residents end up. We can rephrase the problem as finding a permutation ~p_1,\dots,p_N~ with the smallest number of inversions such that the array ~h_i' := (-1)^{|i-p_i|}h_{p_i}~ for ~1 \le i \le N~ is nondecreasing.

We will present the solution to subtasks 5 and 6 first as it helps put all the subtasks into a bigger picture.

Subtasks 5 and 6

Consider the element with the largest ~|h_i|~, say at index ~j~. We must move ~h_j~ to either index ~1~ or ~N~, and it is possible that only one or none of these indices result in ~h_j~ having the correct sign in the end. After doing so, we can effectively ignore ~h_j~ and continue this reasoning recursively on the remaining elements, except for the fact that where ~h_j~ ends up might affect the parity of the final indices of the remaining residents.

This suggests using dynamic programming with a state of the form ~dp[k][b]~, representing the minimum number of swaps to put all the ~k~ largest ~|h_i|~s at an endpoint of the line and with the correct sign, where the number of residents assigned to the left end is ~\equiv b \pmod 2~. Note that it suffices to consider greedily making swaps to move the residents into an endpoint in decreasing order of ~|h_i|~, as every inversion gets accounted for exactly once this way. Let ~l_k~ be the number of residents left of the ~k~th largest ~|h_i|~ with a higher ~|h_i|~ and ~r_k~ be the number of residents right of the ~k~th largest ~|h_i|~ and with a higher ~|h_i|~. The transitions are of the form ~dp[k][b]+l_k \to dp[k+1][b \oplus 1]~ and ~dp[k][b]+r_k \to dp[k+1][b]~, both only considered if the sign is correct. This dynamic programming can be performed in linear time after precalculating ~l_k~ and ~r_k~.

Finding ~l_k~ and ~r_k~ naively takes ~\mathcal{O}(N^2)~ time, which solves subtask 5, and a binary indexed tree similar to inversion counting can be used to find ~l_k~ and ~r_k~ in ~\mathcal{O}(N \log N)~ time, solving subtask 6.

Interlude

The path to the full solution is more clear after solving subtasks 5 and/or 6. We will still use dynamic programming with a similar state, except we need to consider all the residents with the same ~|h_i|~ simultaneously, finding the minimum number of inversions incurred to move all of them to an endpoint while fixing the parity of how many residents are moved towards the left endpoint.

A solution to subtasks 3 and/or 4 will integrate nicely into a full solution, as we can view residents with the same ~|h_i|~ as ~\pm 1~ and residents with smaller ~|h_i|~ in between them as ~0~. Subtasks 1 and 2 are easier versions of this task where ~0~s are not allowed.

Subtasks 1 and 2

Many different perspectives may lead to a solution, some of which are more obviously correct than others. One of the most direct perspectives (working with the original ~h_i~s) can lead to a solution resembling greedy bracket matching. We will present a different perspective that leads more easily to a subtask 3 and 4 solution.

Consider flipping the sign of every other ~h_i~. After this transformation, the swaps become normal swaps that do not flip any signs. There are ~N+1~ candidates for the final configuration of ~h_i~s. For each final configuration, focus on the set of indices where ~h_i = 1~ in the initial and final states, say ~a~ and ~b~. If these sets do not have the same number of elements, then this configuration is unreachable. Otherwise, a swap is equivalent to "shifting" an index by ~1~ to the left or right, and it follows that the answer is ~|a_1-b_1|+|a_2-b_2|+\dots~.

For subtask 1, it suffices to implement the above idea naively in ~\mathcal{O}(N^2)~ time. For subtask 2, note that only one value of ~b_i~ changes each time as we sweep through the possible final configurations, so a running sum can be maintained to solve the problem in ~\mathcal{O}(N)~ time. It may be necessary to consider some cases on whether the number of ~1~s in the initial state (after flipping every other ~h_i~) is one more or less than ~N/2~.

Subtasks 3 and 4

Like in subtasks 1 and 2, we begin by flipping the sign of every other ~h_i~. There are ~N+1-z~ candidates for the final configuration, where ~z~ is the number of ~0~s among ~h_i~.

For subtask 3, we may consider all these candidates independently. For each configuration, we need to solve the following problem:

Given two length ~N~ arrays of elements in ~\{-1,0,1\}~, find the minimum number of swaps required to transform one array into the other.

This problem can be modelled using inversion counting: In both arrays, label the ~-1~s with ~1,2,\dots,x~ from left to right for some ~x~, the ~0~s with ~x+1,\dots,y~ for some ~y~, and the ~1~s with ~y+1,\dots,N~. The answer is the number of inversions between these two permutations. Finding the number of inversions can be done in ~\mathcal{O}(N \log N)~ time using a BIT, for a total time complexity of ~\mathcal{O}(N^2 \log N)~ (since there are only ~3~ distinct elements in the arrays, it is also possible to do this in ~\mathcal{O}(N^2)~ total).

For subtask 4, note that only a few elements change their inversion count each time as we sweep through the possible final configurations, so we can maintain a running sum instead to solve the problem in ~\mathcal{O}(N \log N)~ or ~\mathcal{O}(N)~ time. Similar to subtask 2, it may be necessary to consider some cases on whether ~z~ is odd and whether the number of ~1~s in the initial state is one more or less than ~(N-z)/2~.

Subtasks 7 and 8

To solve subtasks 7 and 8, we can combine the solution for subtasks 3 and 4 with the dynamic programming of subtasks 5 and 6.