Micro's girlfriend Mini wants to go to shopping with Micro. Of course, Micro will be taking care of all her expenses. She wants to go to Code Mall for shopping. There are N shops in the mall, numbered 1 to N. Each shop is having a standard S ,represented by an integer value. Since she understands that Micro is undergoing a financial crisis, she will only go to those shops with standard less than or equal to c, but she wants to go to shops whose number lie between a and b. Now Micro wonders for different given values of a, b and c, how many shops he will have to visit.

Input:
First line consists of two space separated integers N and Q denoting the number of shops and number of queries respectively.
Second line consists of N space separated integers. i^th integer denotes the standard of i^th shop.
Q lines follow each containing three space separated integers a, b and c.

Output:
For each value of a, b and c print the answer in a new line.

Constraints:
1 ≤ N ≤ 100000
1 ≤ Q ≤ 100000
1 ≤ S , c ≤ 1000000000
1 ≤ a ≤ b ≤ N