题目描述

又到了暑假！

又到了西瓜地！

徐老师又双叒来捡西瓜了！

经过无人机的扫描，他发现今年的西瓜地变成了一个包含 $n$ 个西瓜的树形结构

西瓜编号分别为 $1 \sim n$，其中第 $i$ 个西瓜大小为 $a_i$，在西瓜地中有 $n-1$ 条小路，每条小路连接着两个编号 $u,v$ 的西瓜，即可以从 $u$ 号西瓜走到 $v$ 号西瓜，或者从 $v$ 号西瓜走到 $u$ 号西瓜

现在徐老师抱着一个大小为 $z$ 的西瓜不知道从何处走到了 $x$ 号西瓜处，并且他决定沿着一条 简单路径 走到 $y$ 号西瓜处，在移动过程中，徐老师每到达到一个西瓜处，就会拿手里的西瓜和这个位置的西瓜进行比较，如果这个位置的西瓜大小大于他现在手里的西瓜，则他会把手里的西瓜扔下并且拿起这个位置的西瓜

现在徐老师想知道，他一共会替换几次西瓜？

输入格式

输入第一行包含一个整数 $n$ 表示西瓜数量

输入第二行包含 $n$ 个整数 $a_i$ 分别表示每个西瓜的大小

接下来 $n - 1$ 行，每行包含两个整数 $u,v$ 表示一条小路连接的两个西瓜编号

接下来一行输入一个整数 $T$ 表示询问次数

接下来 $T$ 行，每行包含三个整数 $x,y,z$ 含义如题，其中每次询问完全独立

输出格式

对于每次询问，输出一个答案

数据范围

对于 $20\%$ 的数据满足 $2 \leq n, T\leq 100$

对于 $50\%$ 的数据满足 $2 \leq n, T\leq 5000$

对于 $70\%$ 的数据满足 $2 \leq n, T\leq 50000$

对于 $100\%$ 的数据满足 $2 \leq n, T, a_i, z\leq 100000, 1 \leq x,y \leq n$

特别的，保证所有数据一定满足： $y$ 在 $x$ 到 $1$ 的路径上

样例输入1

5
3 5 1 2 4
1 2
1 3
2 4
3 5
4
4 2 1
4 2 2
4 2 3
5 1 5

样例输出1

2
1
1
0