### 问题描述 差点铁三角定义：在一个关系网中，有两个人与同一个人认识，但是他们两个人之间并不认识，这样的关系称之为差点铁三角。 给定一个正整数 $n$ ，代表有 $n$ 个人，他们之间有 $n-1$ 条边，形成树形结构，每个人都有一个自己的价值 $a_i$，**差点铁三角的价值是构成差点铁三角的三个人的价值总和**。现在你想知道在这个树型结构中，所有的差点铁三角的价值的最大值。如果关系网中不存在差点铁三角，则输出 $-1$ 。 ### 输入格式 第一行，一个正整数 $n$ $(1\leq n\leq 10^5)$，代表一共有 $n$ 个人。 第二行，包含 $n$ 个正整数 $a_i$ $(1\leq i\leq n ,1\leq a_i\leq 10^5)$ ，代表第 $i$ 个人的价值为 $a_i$ 。 接下来 $n-1$ 行，每行两个正整数 $l,r$ $(1\leq l,r\leq n)$ ，代表第 $l$ 个人和 $r$ 个人之间有相互认识的关系。 ### 输出格式 一行，包含一个正整数，代表在这张树形关系网中所有的差点铁三角中最大的价值。如果关系网中不存在差点铁三角，则输出 $-1$ 。 ### 样例输入 1 ``` 2 3 6 1 2 ``` ### 样例输出 1 ``` -1 ``` ### 样例输入 2 ``` 4 1 2 3 4 1 3 2 4 3 4 ``` ### 样例输出 2 ``` 9 ``` ### 样例说明 在第一个样例中，关系网中并不存在差点铁三角关系。 在第二个样例中，差点铁三角关系有 $[1,3,4],[3,4,2]$ ，他们的总价值分别是 $[8,9]$ ，他们的最大值为 $9$ ，所以答案为 $9$ 。