To keep track of cubes and their values, use an array ~A~, where the index represents the value of the cube and the element represents the position of the cube in the original line (i.e. ~A_a = b~ means that the cube with value ~a~ is at position ~b~). Notice that for each query, if you were to iterate from position ~a~ to position ~b~, adding each value to a counter, you would run out of time due to the large number of cubes and queries (time complexity ~\mathcal{O}(N \times Q)~).

Instead, use a prefix sum array data structure ~P~, where ~P_i~ equals the sum of all values from cube ~1~ to cube ~i~. Therefore, the sum of all values from cubes ~i~ to ~j~ can be expressed as ~P_j - P_i + V_i~. Proof is left as an exercise for the reader. Preprocessing takes linear time, and each query is constant, meaning that the program should terminate with plenty of time remaining.

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