Maximum Sum of k Elements in a Subarray

You are given an array \(A = [a_0, a_1, \ldots, a_{n-1}]\) of \(n\) integers. You need to answer \(q\) queries.

Each query is described by three integers \(x\), \(y\), and \(k\). For each query, consider the subarray from index \(x\) to \(y\) (inclusive). You can sort this subarray in any order (ascending or descending). Your task is to choose exactly \(k\) elements from the sorted subarray in such a way that the sum of these \(k\) elements is maximized.

Formally, if you denote the sorted subarray as \(B\), then you should select \(k\) elements \(B_{i_1}, B_{i_2}, \ldots, B_{i_k}\) such that \(\sum_{j=1}^{k} B_{i_j}\) is as large as possible. It is optimal to simply sort the subarray in descending order and take the first \(k\) elements.

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains an integer \(n\) (\(1 \leq n \leq 10^5\)) representing the number of elements in the array.
• The second line contains \(n\) space-separated integers \(a_0, a_1, \ldots, a_{n-1}\).
• The third line contains an integer \(q\) (\(1 \leq q \leq 10^5\)) representing the number of queries.
• Each of the next \(q\) lines contains three space-separated integers \(x\), \(y\), and \(k\) (with \(0 \leq x \leq y < n\) and \(1 \leq k \leq y-x+1\)).

outputFormat

For each query, output a single line containing the maximum sum of exactly \(k\) elements chosen (after sorting the subarray in descending order).

## sample

5
4 1 3 2 5
1
0 3 2

7

</p>