Камни Курияма

У Курияма $n$ камней, цена $i$-го камня — $v_i$. Она задаёт вопросы двух типов:

1. 1 l r — сумма $v_l + v_{l+1} + \ldots + v_r$.

Ответьте на все вопросы.

В первой строке $n$ ($1 \le n \le 10^5$). Во второй — $n$ целых чисел $v_i$ (). В третьей — (). В следующих строках , , (, ).

Для каждого вопроса одно число в отдельной строке.

Постройте два массива префиксных сумм: для исходного массива и для отсортированной копии. Каждый вопрос — $p_r - p_{l-1}$ в нужном массиве. Сортировка заново в каждом вопросе — $O(m \cdot n \log n)$, слишком медленно.