For a subarray, define its power as the sum over every distinct value v in it of cnt(v) * cnt(v) * v, where cnt(v) is how many times v appears in that subarray. For example, [1, 2, 1] has power 2*2*1 + 1*1*2 = 6.
Given an array nums of positive integers and a list queries of [l, r] pairs (inclusive), return the power of nums[l..r] for every query, in the order the queries were given.
- The array never changes and all queries are known in advance
- Moving the window by one element changes the power by a simple formula; Mo's algorithm sorts the queries so that the window moves little in total
- Target: about O((n + q) sqrt(n)) element moves