题目描述

当一棵二叉树满足对于任意子树，其左子树（若有）中节点的值均不大于该节点的值，右子树（若有）中节点的值均不小于该节点的值，则我们称这棵树为二叉搜索树。

进一步地，若这棵树还满足对于任意节点，其左子树高度与右子树高度的差的绝对值均不大于 $1$，则我们称这棵树为一棵 AVL 树。

若左（或右）子树不存在，则我们视其高度为 $0$。

现在请你对于指定的一棵二叉树，找出它最大（即节点最多）的一棵满足 AVL 树性质的子树的大小。

输入格式

第一行一个正整数 $n$ ($1 \leq n \leq 5 \cdot 10^5$)，表示这棵二叉树有 $n$ 个节点，从 $1$ 到 $n$ 进行编号。

第二行 $n$ 个正整数，用一个空格隔开，第 $i$ 个数 $a_i$ ($1 \leq a_i \leq 10^6$) 表示编号为 $i$ 的节点的权值。

接下来 $n - 1$ 行，每行三个整数 $u$ ($1 \leq u \leq n$)，$v$ ($1 \leq v \leq n$, $u \neq v$)，$w$ ($0 \leq w \leq 1$)，用一个空格隔开，表示编号为 $v$ 的节点是编号为 $u$ 的节点的子节点。若 $w = 0$ 则它是左儿子，否则为右儿子。

输入数据保证这是一棵合法的二叉树。

输出格式

一行一个正整数 $x$，表示给定二叉树最大的 AVL 子树的大小。

样例

样例输入

6
7 6 5 7 3 8
2 4 1
1 6 1
3 5 0
1 2 0
3 1 1

样例输出

4