RoAlgo Contest #4 (incepatori) | chmax

Raul and Deniz are playing True or False. Being computer scientists, they changed the game's settings, and now the questions are different. The game now proceeds as follows:

1. Raul and Deniz receive the numbers $N$, $Q$, and a sequence $a_1 \ a_2 \ \dots \ a_N$ of natural numbers.
2. There are $Q$ questions of the form: "Given the numbers $l$, $r$, and $p$ ($1 \leq l \leq p \leq r \leq N$). Tell if $a_p$ is equal to $max(a_l, a_{l+1} \dots a_r)$". Raul and Deniz need to quickly determine if they should say True or False.

Task

To answer these questions very quickly, they asked you to help write a program that responds as quickly as possible to these queries.

Input data

The first line contains two natural numbers, $N$ and $Q$.

The second line contains $N$ natural numbers, representing the sequence $a_1 \ a_2 \ \dots \ a_N$.

The next $Q$ lines each contain a triplet of numbers, representing $l$, $r$, and $p$ in this order.

Output data

Print a sequence of $Q$ characters, with the $i$-th character being $1$ if the answer to the $i$-th query is true, and $0$ otherwise.

Constraints and clarifications

• $1 \leq N, Q \leq 10^6$
• $a_i \leq 10^9$
• It is recommended to print the entire sequence of characters ($0$ or $1$) once, at the end of the queries

Example 1

stdin

8 12
1 5 5 2 4 9 3 2
1 2 2
1 2 1
2 3 2
2 3 2
2 4 3
2 4 4
2 4 2
1 6 6
7 8 8
4 5 4
3 6 3
3 6 6

stdout

101110110001

Explanation

$N = 8$, $Q = 12$

$a = [1, 5, 5, 2, 4, 9, 3, 2]$

The answer to the first query is true because $l = 1$, $r = 2$, $p = 2$, $a_p = 5$, and $max(a_1, a_2) = max(1, 5) = 5$. So, $a_2 = max(a_1, a_2)$. Therefore, the character to be printed is $1$.

The answer to the second query is false because $l = 1$, $r = 2$, $p = 1$, $a_p = 1$, but $max(a_1, a_2) = 5 \neq a_1$. Therefore, the character to be printed is $0$.

The answer to the fifth query is true because $l = 2$, $r = 4$, $p = 3$, and $a_p = a_3 = max(a_2, a_3, a_4) = max(5, 5, 2) = 5$. Therefore, the character to be printed at the fifth position is $1$.