Problem Author: Shridhar Ravi
TML is around the corner and GSTians are excited about it. Omkar has been chosen as the Fest Coordinator this year. He has introduced a new system of participating in the events this TML.
There are N different events with some entry fees. With this new system of his, students can buy an Entry card worth Rs. K. But, this card is non-rechargeable and can be used exactly for 2 events, such that the entry fees of both the events are not greater than Rs. K.
Omkar has listed all the events and their entry fees and has Q queries. He has specified a range of events, from L to R (both L and R inclusive). He needs your help to know how many different combinations of events a student can participate in the specified range for a card worth Rs. K.
The first line of the input contains two space-separated integers N and Q, denoting the number of events and the number of queries respectively.
The next line contains N space-separated integers denoting the entry fees of each event.
The next Q lines contain 3 space-separated integers L, R, and K denoting the range and worth of the entry card respectively.
For each query Q, output the integer denoting the different combinations of events possible.
1 ≤ N ≤ 10^3
1 ≤ Q ≤ 10^3
1 ≤ L ≤ R ≤ N
1 ≤ Entry fee ≤ 10^3
1 ≤ K ≤ 2*(10^3)
5 1 2 3 2 3 1
1 4 3
1 5 4
2 7 3
For the 1st query, there is only one combination possible in the given range:
2nd event (Fee: 1) + 3rd Event (Fee: 2)=3
For the 2nd query, there are 4 combinations possible in the given range:
2nd event (Fee: 1) + 3rd Event (Fee: 2)=3 (which is less than card’s worth K=4)
2nd event (Fee: 1) + 4th Event (Fee: 3)=4
2nd event (Fee: 1) + 5th Event (Fee: 2)=3 (which is less than card’s worth K=4)
3rd event (Fee: 2) + 5th Event (Fee: 2)=4