2025：开飞机

有 $n$ 个区域，蒜头君可以在这些区域飞行，这些区域编号为 $1$ 到 $n$。对于每个区域 $i$，由于地形限制，蒜头君在该区域内飞行的最低高度为 $a_i$

此外，由于风力条件和蒜头君缺乏飞行经验，他只能在某些成对区域之间飞行。

共有 $m$ 对这样的区域对，编号为 $1$ 到 $m$，第 $j$ 对 $u_j$ 和 $v_j$ 表示蒜头君可以在区域 $u_j$ 和 $v_j$ 之间双向飞行。通过这些区域对，这 $n$ 个区域可以互相到达。

最初，蒜头君位于区域 $1$，高度为 $0$。他想要前往区域 $n$，并且着陆必须以高度 $0$ 结束。

在一分种内，蒜头君可以选择留在当前位置或前往另一个区域。

在同一分种内，他的高度可以增加 $1$ 或减少 $1$ 或保持不变。然而，蒜头君到达一个区域时，他的高度必须至少达到区域要求的最低高度。请问蒜头君需要最少多少时间才能在区域 $n$ 着陆？

第一行输入两个正整数 $n,m$

第二行输入 $n$ 个整数 $a_i$

接下来 $m$ 行每行输入一对 $u_j,v_j$

对于 $100\%$ 数据，$1\le n\le 2\times 10^5, 1\le m\le 4\times 10^5, 0\le a_i\le 10^9, a_1=a_n=0$

3 2
0 2 0
1 2
2 3

4

11 12
0 0 0 0 0 0 2 2 1 5 0
1 2
2 3
3 4
4 5
5 6
6 11
1 7
7 8
8 9
9 11
1 10
10 11

5