Sum of Minimum K Elements in a Subarray

Given an array of integers and a number of queries, your task is to compute, for each query, the sum of the smallest k elements in the specified subarray.

For each query, you are given three integers l, r and k, which represent that you need to consider the subarray \(S = [a_l, a_{l+1}, \dots, a_r]\) (the indices are 1-based). Then, sort \(S\) in non-decreasing order, and calculate the sum of the first \(k\) elements. If \(k\) is larger than \(|S|\) (the length of the subarray), sum all elements in \(S\).

Note: All indices in the queries use 1-based indexing.

The formula for a query can be expressed in LaTeX as follows:

\[ f(l, r, k) = \sum_{i=1}^{\min(k, r-l+1)} s_i \] where \(s_1 \le s_2 \le \cdots \le s_{r-l+1}\) are the sorted values of \(S = [a_l, a_{l+1}, \dots, a_r]\).

inputFormat

The input is read from standard input (stdin) and has the following format:

n
a1 a2 ... an
q
l1 r1 k1
l2 r2 k2
...
lq rq kq

where:

• \(n\) is the number of elements in the array.
• \(a1, a2, \dots, an\) are the integers in the array.
• \(q\) is the number of queries.
• Each query is represented by three integers: \(l\), \(r\), and \(k\).

outputFormat

For each query, output the sum of the smallest \(k\) elements of the subarray defined by the indices \(l\) and \(r\). The answers for each query should be printed on a separate line to standard output (stdout).

## sample

7
4 2 5 1 6 7 3
4
1 3 2
4 5 1
2 7 3
1 7 4

6
1
6
10

</p>