ADATREE - Ada and Trees

Ada the Ladybug is a farmer. She has a long furrow in which she grows trees. Each tree has some weight. 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*105, the number trees and the number of questions.

The next line will contain N integers 0 ≤ Ai ≤ 106, 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 ≤ 106

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

Added by:Morass
Date:2017-10-08
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Tunisian Collegiate Training Contest - Round #01

hide comments
2022-01-04 05:26:52
For those who are stuck <snip>

I tried Mo's algorithm, it won't work (TLE), just saying :)

Last edit: 2022-01-05 02:58:01
2021-09-23 10:07:19
persistent segment tree
2020-07-27 06:05:00
Handle it as offline query. Sort + segment tree. Great problem!
2019-11-22 05:35:23
great problem indeed
approach : SegmentTree +mergeSort +binary Search
2019-09-11 13:44:59
Great problem!!
2019-03-29 15:32:51 DK...
Solutions like O(nsqrt(n)) or O(nlog^2(n)) don't pass for me, I got AC with Persistent segment tree, it could be overkill.

Last edit: 2019-03-29 15:36:38
2018-08-12 10:49:22 DOT
Square root decomposition doesn't produce the best time for me, but it does work. Maybe, try tweaking the block sizes and compare the results.

Last edit: 2018-08-12 10:50:09
2018-06-28 14:45:46
@rajcoolaryan: Good day to you! Can't say whether it is enough.. I would have guessed it might be, yet all judge solutions are faster than this :'(
2018-06-21 06:30:28
square root decmposition tle
2017-10-18 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 :)

Good Luck & Have Nice Day!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.