给定一棵包含 $n$ 个顶点的树，树是一个连通无向图，有 $n$ 个顶点和 $n-1$ 条边。每个顶点都有一个权值 $b_i$。对于任意两个顶点，它们之间存在唯一的一条简单路径，简单路径不包含重复的边。简单路径的长度定义为路径中包含的边数。

你需要选择一条长度不小于 1 的简单路径，并选择一个实数 $x$。设 $V$ 为该简单路径上的顶点集合。你需要计算下式的最大值： $$\frac{\sum_{u \in V} (-x^2 + b_u x)}{|V|}$$

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示树的顶点数。 第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($-10^5 \le b_i \le 10^5$)，表示每个顶点的权值。 接下来的 $n-1$ 行，每行包含两个整数 $u, v$，表示树中的一条边。

输出格式

输出一个实数，表示答案。 如果你的答案与正确答案的绝对误差不超过 $10^{-4}$，则视为正确。

样例

样例输入 1

2
3 2
1 2

样例输出 1

1.562500