ADATREE  Ada and Trees
Ada the Ladybug is a farmer. She has a long furrow in which she grows trees. Each tree has some weigth. The task is simple, she wants to know the biggest tree on some part of the furrow which is not greater than some height H. As Ada asks for this very often, she asked you to write a program for this.
Input
The first line will contain two integer 1 ≤ N, Q ≤ 3*10^{5}, the number trees and the number of questions.
The next line will contain N integers 0 ≤ A_{i} ≤ 10^{6}, the heights of trees.
The sum next Q will contain three integers: 0 ≤ l ≤ r < N, the segment of furrow she is interested in and 0 ≤ H ≤ 10^{6}
Output
For each query output either the size of highest tree lesser/equal to H or output 0 if such tree doesn't grow on given segment.
Example Input
9 8 1 5 9 11 9 7 6 2 1 1 6 4 1 6 10 0 8 97 0 8 4 1 4 5 2 6 8 2 8 5 3 3 12
Example Output
0 9 11 2 5 7 2 11
hide comments
morass:
20171018 23:28:31
@shubham_001: Good day to you. No judge solution uses treap. I could imagine a solution using it, but I don't think it is the "best" way :)


shubham_001:
20171018 16:10:36
is this a treap question? 
Added by:  Morass 
Date:  20171008 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Tunisian Collegiate Training Contest  Round #01 