404194: GYM101446 H Flooding

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Floodingtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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 ≤ 106).

Second line consists of n integers a1, a2, ..., an (0 ≤ ai ≤ 109) that describe objects in the forest. If ai = 0, there is a water source at i-th region, otherwise there is a tree of height ai.

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 ≤ 109).

Output

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

ExampleInput
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
Output
Yes
No
No
Yes
No
Yes
No

加入题单

上一题 下一题 算法标签: