题目描述

又到了暑假，小A又来到西瓜地！

经过无人机的扫描，他发现今年的西瓜地形成了一棵包含 $n$ 个节点的树。节点编号为 $1\sim n$，第 $i$ 个节点上有一个大小为 $a_i$ 的西瓜。树上的 $n-1$ 条小路连接各个节点，每条小路可以双向通行。

每次询问中，小A手里抱着一个大小为 $z$ 的西瓜，沿树上从节点 $x$ 到节点 $y$ 的简单路径行走。保证 $y$ 在 $x$ 到节点 $1$ 的路径上，允许 $x=y$。

小A会依次比较路径上每个节点的西瓜，起点 $x$ 和终点 $y$ 也要比较。如果当前节点的西瓜严格大于手中的西瓜，他就扔下手中的西瓜，换成当前节点的西瓜；大小相等时不替换。

请回答每次询问中，小A一共替换多少次西瓜。每次询问相互独立，均使用给定的初始大小 $z$ 和原始节点大小 $a_i$。

输入格式

从文件 sesame.in 中读入数据。

第一行包含一个整数 $n$，表示节点数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各节点的西瓜大小。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示节点 $u$ 与节点 $v$ 之间有一条小路。保证这些小路构成一棵树。

接下来一行包含一个整数 $T$，表示询问数量。

接下来 $T$ 行，每行包含三个整数 $x,y,z$，含义如题目描述所述。

输出格式

输出到文件 sesame.out 中。

输出 $T$ 行，每行一个整数，表示对应询问中的替换次数。

样例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

样例解释1

第一条询问依次比较节点 $4,2$ 上大小为 $2,5$ 的西瓜。初始大小为 $1$，因此两次都替换。

第二条询问的初始大小为 $2$，在节点 $4$ 不替换，在节点 $2$ 替换一次。第三条询问也只在节点 $2$ 替换。

第四条询问经过的节点依次为 $5,3,1$，对应大小为 $4,1,3$，都不超过初始大小 $5$，因此答案为 $0$。

样例 2

见选手目录下的 sesame/sesame2.in 与 sesame/sesame2.ans。

该组样例满足 $n,T\le5000$。

样例 3

见选手目录下的 sesame/sesame3.in 与 sesame/sesame3.ans。

该组样例满足 $n,T\le50000$。

数据范围

对于所有测试点，保证 $2\le n,T\le100000$，$0\le a_i\le100000$，$1\le z\le100000$，$1\le u,v,x,y\le n$。保证输入是一棵树，且 $y$ 在 $x$ 到节点 $1$ 的路径上。

各测试点的额外规模限制如下。

测试点编号	$n,T$ 的上限
$1\sim4$	$100$
$5\sim10$	$5000$
$11\sim14$	$50000$
$15\sim20$	$100000$