RoAlgo Contest #10 | arborel

Returning to Moldova, Alexandru Lăpușneanu wants to take revenge on the boyars in a draconic manner, and the only way they can escape the wrath of the ruler is by solving the following problem:

Task

Given a tree with $N$ nodes rooted at node $1$, each node $i$ having an associated value $v_i$. There are $Q$ queries of the form: $x, l, r$ ($l \leq r$), which ask how many nodes in the subtree of node $x$ have values between $l$ and $r$ (inclusive).

Input data

The first line contains the natural number $N$. The second line contains $N$ natural numbers $v_1, v_2, ..., v_N$ - the values associated with the $N$ nodes. The next $N-1$ lines contain two natural numbers $u$ and $v$, indicating that there is an edge in the tree between nodes $u$ and $v$. The next line contains the natural number $Q$, representing the number of queries. The next $Q$ lines contain three natural numbers $x, l, r$ as described in the statement.

Output data

The output will consist of $Q$ lines, where the $i$-th line contains the answer to the $i$-th query.

Constraints and clarifications

• $1 \leq N \leq 150\ 000$
• $1 \leq Q \leq 150\ 000$
• $1 \leq v_i \leq 10^9$ for $1 \leq i \leq N$
• For tests worth $20$ points, $1 \leq N \leq 1000$ and $1 \leq Q \leq 1000$
• Additional tests were added after the contest

Example

stdin

5
10 17 10 19 4
2 1
1 3
2 4
2 5
3
2 6 19
1 11 17
1 4 19

stdout

2
1
5