To solve the first subtask, it was sufficient to fix each possible number of parallel blind lifts for each query, and then by traversing the blinds, determine how many manual blind lifts are needed. Time complexity: ~\mathcal{O}(n \times q \times maxa)~.

Subtask ~q = 1~ could be solved in a similar way. Instead of traversing the blinds to determine the number of manual lifts, we will sort the blinds in descending order at the beginning. Now we can notice that some prefix of the blinds will always need to be manually lifted. We can find exactly which prefix by using binary search. To determine how much time will be needed, we will use prefix sums. Time complexity: ~\mathcal{O}(q \times maxa \times \log n)~.

The entire task could be solved in two completely different ways. The first method, which we won't go into depth in here, is to notice that the function of cost depending on the number of parallel lifts is convex. By using ternary search, we can determine the most efficient solution for each query.

For the second method, we will compute the solution for every possible blind height. Let's assume that for a certain height ~h~, we have calculated the fastest way to lower all blinds so that all are lowered by at most ~h~ centimeters. Let the blinds then be in the state ~b_1, b_2, \dots, b_n~. It obviously holds that ~b_1, b_2, \dots, b_n \le h~. We want to go from this state to a state that has max height of ~h-1~. To do this we will perform one of the following two operations:

• We will raise all blinds parallel by ~1~ centimeter, thus reaching a state where the maximum height is ~h-1~.
• We will manually lower all blinds with a height of ~h~ by ~1~ centimeter.

Choosing the operation that takes less time, it holds that this will be the best way to reach the state ~h-1~. Proof is left as an exercise for the reader.

If we start from the highest possible height, we can build solutions towards smaller heights. Time complexity: ~\mathcal{O}(maxa)~.