Go Back
TML Events (100)
Description

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.

Input

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.

Output

For each query Q, output the integer denoting the different combinations of events possible.

Constraints

1 ≤ N ≤ 10^3
1 ≤ Q ≤ 10^3
1 ≤ L ≤ R ≤ N
1 ≤ Entry fee ≤ 10^3
1 ≤ K ≤ 2*(10^3)

Example
Copy Input

Input:
7 3
5 1 2 3 2 3 1
1 4 3
1 5 4
2 7 3
Output:
1
4
5

Explanation

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

Good Bye Batch 15-19
#OneLastTime Contest from Batch of 2015-19 of SIES GST



Announcement
Surprise Problem Added!
Contest is extended by 24 hours!

Problem Tags
adhoc, math

Supported by our Coding Partner