给定一棵二叉树，请求出它的最大宽度。

某一层的宽度，是这一层最左侧非空节点和最右侧非空节点之间所占的位置数量。计算时要把两端之间原本应该存在的空位置也计入宽度，就像把这棵树放进一棵无限完全二叉树中一样。最终答案是所有层宽度的最大值。

输入格式

第一行一个整数 $n$，表示二叉树的节点数。节点编号为 $1$ 到 $n$，根节点编号为 $1$；当 $n=0$ 时表示空树。

当 $n>0$ 时，第二行包含 $n$ 个整数 $v_1,v_2,\ldots,v_n$，其中 $v_i$ 表示节点 $i$ 保存的值。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i,r_i$，分别表示节点 $i$ 的左孩子编号和右孩子编号。编号 $0$ 表示相应孩子不存在。输入保证这些数据构成一棵合法二叉树。

输出格式

输出一个整数，表示二叉树的最大宽度。

6
-14 -21 -4 -4 3 -10
2 3
0 0
4 5
6 0
0 0
0 0

2

6
-22 -7 -28 -18 -19 -21
2 3
4 0
0 0
5 0
0 6
0 0

2

8
-3 11 -7 -9 -24 -19 -2 10
2 0
0 3
4 5
6 0
7 8
0 0
0 0
0 0

4

数据范围与约定

• 树中节点的数目范围是 [1, 3000]
• -100 ≤ v_i ≤ 100