Kuriyama's stones

Kuriyama has $n$ stones; stone $i$ costs $v_i$. She asks questions of two types:

1. 1 l r — the sum $v_l + v_{l+1} + \ldots + v_r$.
2. 2 l r — the sum of the costs of stones $l$ through $r$ if the stones are sorted by cost in increasing order.

Answer every question.

The first line contains $n$ ($1 \le n \le 10^5$). The second line contains $n$ integers $v_i$ ($1 \le v_i \le 10^9$). The third line contains $m$ ($1 \le m \le 10^5$). The next $m$ lines contain $t$, $l$, $r$ ($t \in \{1, 2\}$, $1 \le l \le r \le n$).

For every question print one number on a separate line.

Build two prefix sum arrays: one for the original array and one for a sorted copy. Every question is $p_r - p_{l-1}$ in the right array. Sorting again for every question is $O(m \cdot n \log n)$ — too slow.

The sum reaches $10^{14}$ — a 64-bit type is needed. In the first example the sorted array is $2, 2, 4, 6, 7, 7$, and the first question is $4 + 6 + 7 + 7 = 24$.

Source: Codeforces, problem 433B.