题目描述

兔子 Benson 正要启动飞机！

有 $n$ 块 Benson 可以飞入的区域，由 $1\sim n$ 编号。受地形限制，进入第 $i$ 块区域时，需要保证飞机的高度不低于 $a_i$。保证 $a_1=a_n=0$。

此外，由于风况复杂而 Benson 的经验尚不充足（毕竟他是只兔子），他只能在某些特定的航线上双向飞行。具体地，有 $m$ 条航线，由 $1\sim m$ 编号，其中第 $i$ 条航线 $u_j,v_j$ 表示 Benson 可以在这两块区域间直接飞行。

Benson 发现，他可以通过在直接的航线上飞行，使得这些区域两两可达。

现在，Benson 在 $1$ 号区域，高度为 $0$。他希望降落在 $n$ 号区域，高度自然也为 $0$。每一分钟，Benson 可以跨过一条航线或不移动，并同时使飞机的高度上升 $1$、下降 $1$ 或保持不变。注意，当他到达 $i$ 区域时，必须保证飞机的高度不低于 $a_i$。

Benson 想知道，从 $1$ 号区域出发，在 $n$ 号区域降落，所需的最小时间。

输入格式

第一行两个正整数 $n, m$，用空格隔开。

接下来一行 $n$ 个整数 $a_1, a_2,\cdots, a_n$，表示区域的高度限制。

接下来 $m$ 行，每行两个正整数 $u_j,v_j$，表示一条在 $u_j,v_j$ 间的双向航线。

输出格式

一行一个整数，表示 Benson 所需的最小时间。

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

提示

样例 #1 解释

Benson 从 $1$ 出发，在 $3$ 降落，总共需要 $4$ 分钟：

• 第 $1$ 分钟，Benson 不移动，同时高度从 $0$ 变为 $1$；
• 第 $2$ 分钟，从 $1$ 移动到 $2$，同时高度从 $1$ 变为 $2$；
• 第 $3$ 分钟，从 $2$ 移动到 $3$，同时高度从 $2$ 变为 $1$；
• 第 $4$ 分钟，Benson 不移动，同时高度从 $1$ 变为 $0$。

数据范围

对于 $100\%$ 的数据：

• $1\leq n\leq 2\times 10^5$
• $1\leq m\leq 4\times 10^5$
• $0\leq a_i\leq 10^8$，$a_1=a_n=0$
• $1\leq u_j,v_j\leq n$，$u_j\ne v_j$