P11535 [NOISG 2023 Finals] Airplane

兔子 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 所需的最小时间。

#### 样例 #1 解释 Benson 从 $1$ 出发，在 $3$ 降落，总共需要 $4$ 分钟： - 第 $1$ 分钟，Benson 不移动，同时高度从 $0$ 变为 $1$； - 第 $2$ 分钟，从 $1$ 移动到 $2$，同时高度从 $1$ 变为 $2$； - 第 $3$ 分钟，从 $2$ 移动到 $3$，同时高度从 $2$ 变为 $1$； - 第 $4$ 分钟，Benson 不移动，同时高度从 $1$ 变为 $0$。 #### 数据范围 | Subtask | 分值 | 特殊限制 | | :-----------: | :-----------: | :-----------: | | $0$ | $0$ | 样例 | | $1$ | $22$ | $m=n-1,u_j=j,v_j=j+1$ | | $2$ | $10$ | $n\leq 2000$，$m\leq 4000$，$a_i\leq 2000$ | | $3$ | $31$ | $n\leq 2000$，$m\leq 4000$ | | $4$ | $37$ | 无 | 对于 $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$