The Logging Company has been hit with a petition from concerned citizens regarding their uncontrolled tree-cutting. For public relations purposes, they have decided that, moving forward, they will only cut down trees with mass above a certain threshold.
The Logging Company has a line of 
~N~ 
~(1 \le N \le 100\,000)~ trees. Each tree 
~i~ has a mass 
~m_i~ 
~(1 \le m_i \le 20\,000)~. The Company wants to cut some of the trees, so they've hired you to calculate the mass of all the wood they would get from cutting all the trees with ~m_i~ greater than or equal to 
~q~ 
~(1 \le q \le 20\,000)~ between positions 
~a~ and 
~b~ inclusive 
~(0 \le a \le b < N)~. In particular, they want you to answer 
~Q~ 
~(1 \le Q \le 100\,000)~ such queries.
Input Specification
The first line will contain the integer ~N~. For each tree ~i~, the 
~i^{th}~ (from 0) integer on the second line will contain the integer mass ~m_i~. The third line will contain the number ~Q~, the number of queries the logging company wants you to answer. The next ~Q~ lines will contain three integers ~a~ and ~b~ and ~q~.
Output Specification
For each query, print the total mass of the trees at position ~i~ such that 
~a \le i \le b~, and 
~m_i \ge q~.
Sample Input
5
1 3 4 2 5
5
0 4 3
1 3 2
0 4 5
4 4 1
0 4 1
Sample Output
12
9
5
5
15
Comments
Is there somewhere you can find test cases for DMOPC problems?
You should learn how to come up with testcases on your own -- after all, most contests won't be nice enough to give you access to their test cases.
ok, thanks