AT_pakencamp_2024_day3_2_e Roller Coaster

遊園地「パ研ランド」には、 $ N $ 個の地点があり、 $ i $ 番目の地点の高度は $ H_i $ です。また、園内には $ M $ 本のジェットコースター用レールが敷かれており、 $ i $ 番目のレールは地点 $ U_i $ と $ V_i $ を双方向に結んでいます。 あなたは、これらのレールのいくつかを使って、以下の条件を満たすジェットコースターの経路を構築しようと考えています。 - 通る地点の順序を $ v_0, v_1, \dots, v_n $ とすると、 $ v_0 = v_n $ が成り立つ。 - すべての $ i $ ( $ 1 \leq i \leq n $ ) について、 $ v_{i-1} $ と $ v_i $ を直接結ぶレールが存在する。 また、ジェットコースターの **楽しさ** を以下の式で定義します。 \\\[ \\frac{1}{n} \\sum\_{i=1}^{n} \\max(0, H\_{v\_{i-1}} - H\_{v\_i}) \\\] 楽しさの最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ H_1 $ $ H_2 $ $ \ldots $ $ H_N $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_M $ $ V_M $

答えを出力せよ。真の値との絶対誤差または相対誤差が $ 10^{-9} $ 以下の場合正答と判定される。

### Sample Explanation 1 例えば、 $ 4, 3, 2, 1, 4 $ の順番で通るジェットコースターは問題文中の条件を満たします。その楽しさは、 - $ H_4 - H_3 = 1 $ - $ H_3 - H_2 = 1 $ - $ H_2 - H_1 = 1 $ - $ H_1 - H_4 = -3 $ であることから、 $ (\max(0, 1) + \max(0, 1) + \max(0, 1) + \max(0, -3)) $ を $ 4 $ で割った値、すなわち $ 0.75 $ になります。 楽しさが最大となるように経路を構築すれば、その値は $ 1.5 $ になります。 ### Sample Explanation 2 遊園地の地点の組であって、レールのみでは接続されていないようなものが存在する可能性もあります。 ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq M \leq 2 \times 10^5 $ - $ 1 \leq H_i \leq 10^9 $ ( $ 1 \leq i \leq N $ ) - $ 1 \leq U_{i} \lt V_{i} \leq N $ ( $ 1 \leq i \leq M $ ) - $ i \neq j $ ならば、 $ (U_{i}, V_{i}) \neq (U_{j}, V_{j}) $ - 入力は全て整数