Queries in an Array ( Nium Inc.)

 Chef has an array 

a$a$ consisting of positive integers. This array is sorted in non-decreasing order from left to right.

You are given Q$Q$ queries. Each query consists of three integers l,r,x$l,r,x$. The answer to this query can be found as follows. Consider the subarray al,al+1,…,ar$a_l,a_{l+1},\dots ,a_r$. The answer to the query is the count of numbers in this subarray that are greater than or equal to x$x$.

Input Format

• The first line of each test case contains two space-separated integers n,Q$n,Q$.
• The second line contains n$n$ space separated integers denoting the array a$a$.
• Each of the next Q$Q$ lines contains three space-separated integers l,r,x$l,r,x$ denoting the query.

Output Format

Output Q$Q$ lines one for each query containing the answer for the corresponding query.

Constraints

• 1≤n,Q≤105$1\le n,Q\le {10}^5$
• 1≤ai≤109$1\le a_i\le {10}^9$
• 1≤l≤r≤n$1\le l\le r\le n$
• 1≤x≤109$1\le x\le {10}^9$

Subtasks

• For 10%$10\mathrm{\%}$ of the score: 1≤n,Q≤100$1\le n,Q\le 100$
• For 20%$20\mathrm{\%}$ of the score: 1≤x≤100$1\le x\le 100$
• Remaining 70%$70\mathrm{\%}$: No extra constraints.

Sample Input 1 

5 6
1 2 3 6 9
1 5 1
1 5 3
1 5 10
1 4 4
2 5 4
2 5 1

Sample Output 1 

5
3
0
1
2
4

Explanation

• For the first query, all the elements of the array are ≥1$\ge 1$. Thus, the answer is 5$5$.
• For the second query, the answer will be 3$3$, as the elements 3,6,9$3,6,9$ are >3. ≥3

• Tweet
• Share
• Share
• Share
• Share

Related Post