Subtask 1

For each query, sum the cost from each house to ~h_i~ via simulation.

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

Subtask 2

For each query, use a pointer on the left and right side of ~h_i~ to simulate the cost.

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

Subtask 3

For the final subtask, there are a few different solutions. One solution involves building a prefix sum array and suffix sum array where:

~\text{psa}_i = \begin{cases} 0 & \text{if } i = 1 \\ \text{psa}_{i-1} + \text{abs}(a_i - a_{i-1}) \times (i-1) & \text{if } 1 < i \le N \end{cases}~

~\text{ssa}_i = \begin{cases} 0 & \text{if } i = N \\ \text{ssa}_{i+1} + \text{abs}(a_i - a_{i+1}) \times (N-i) & \text{if } 1 \le i < N \end{cases}~

The answer for each query is ~\text{psa}_{h_i} + \text{ssa}_{h_i}~. Note that the above solution uses ~1~-indexed arrays.

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