404194: GYM101446 H Flooding

The Flatland Forest can be represented as a one-dimensional segment divided into regions, with either a tree or a water source in each region. Trees have positive height, each water source is located on the ground, that is, at height 0.

Sometimes a flood happens in the forest. The water starts spreading from the water sources to both sides. If H ≥ 0 is the water level height, then the water floods all regions until it encounters a tree with height at least H or a border of the segment. A region is considered wet if it is flooded by at least one source. Note that the regions containing are wet even when H = 0.

You must answer the following queries: given L, R and H, check if at least one region between regions L and R (inclusive) is wet.

First line of the input contains two integers n and m — the number of regions in the forest and number of queries, respectively (1 ≤ n, m ≤ 10⁶).

Second line consists of n integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁹) that describe objects in the forest. If a_i = 0, there is a water source at i-th region, otherwise there is a tree of height a_i.

Each of the next m lines describes one query and contains three space-separated integers L, R, H — number of leftmost and rightmost region in the segment and the water level height (1 ≤ L ≤ R ≤ n, 0 ≤ H ≤ 10⁹).

For each query print "Yes" if there is at least one wet region among regions L through R, and "No" otherwise.

6 7
0 2 3 1 4 0
1 1 0
4 4 2
2 5 2
2 5 3
3 5 3
3 5 4
5 5 4

Yes
No
No
Yes
No
Yes
No