喵国有 $n$ 个村镇，由 $n-1$ 条无向道路连通。来自喵哈哈村的小喵喵想要周游各地。
旅途的路非常漫长，小喵喵决定在路上买一些宝石收藏，其中第 $i$ 个村镇的宝石价格为 $A_i$。
小喵喵的策略是这样的：在一个起点村落购买宝石，之后路上如果当前的村落的宝石价格比小喵喵手上最贵的宝石贵，那么小喵喵就会购买当前村落的宝石。
现在小喵喵有 $q$ 次独立的旅行（即进行新的一次旅行时手上的宝石都会消失），小喵喵想知道如果从 $u$ 村落沿最短路旅行到 $v$ 村落会购买多少次宝石。
输入格式
第一行为 $1$ 个正整数 $N$。
第二行为 $N$ 个正整数 $A_i$。
第三行至第 $N+1$ 行每行两个正整数 $x_i、y_i$，表示 $x_i$ 和 $y_i$ 之间有一条道路。
第 $N+2$ 行为一个正整数 $Q$。
接下来 $Q$ 行每行一个正整数 $u_i、v_i$，表示一次询问。
输出格式
$Q$ 行每行一个正整数，表示答案。
样例
input
5 4 2 2 3 1 1 2 1 3 3 4 3 5 4 1 1 4 2 5 4 1 5
output
1 2 3 1
限制与约定
对于 $20\texttt{%}$ 的数据，$1 \leq N、Q \leq 2501$。
对于另外 $15\texttt{%}$ 的数据，所有$u_i=1$。
对于另外 $15\texttt{%}$ 的数据，所有$v_i=1$。
对于另外 $40\texttt{%}$ 的数据，$1 \leq N、Q \leq 152501$，所有$y_i=x_i+1$。
对于 $100\texttt{%}$ 的数据，$1 \leq N、Q \leq 252501$，$1 \leq A_i \leq 10^9$，$1 \leq u_i、v_i、x_i、y_i \leq N$。
时间限制：$3\texttt{s}$
空间限制：$64\texttt{MB}$
