这种每一步能上下移动 $1$ 或不动的题，有一个结论是我们可以一直上移到某个位置，停滞不超过 $1$ 单位时间然后再下移。这个结论很好理解：我们如果飞到某个不一定需要往下飞的位置往下一定不优，如果是一个能往上飞的位置那么停滞也一定不优。

所以我们一定是一直往上飞直到不能再飞了（因为我们还要降落，不能一直往上飞）然后不断下降，这样最多也就是路径最中间有 $1$ 的停滞时间。

有了这个性质题目就有一点改变：如果我们枚举最中间的点或边，那么就剖分成了两个问题，且两个问题都是要求从某个起点开始，往上一直飞到达每个点的所需要的最小时间。

然后我们发现，对于这个问题，若到达某个点的一种方案所需的时间不是最少的那它往后传递也不会是最优的，所以这个问题可以用类似 dijkstra 的方法解决。

最后合并答案，枚举点的话就是前后两个方案的最大值乘 $2$（必须要把小的一遍抬升到和大的一样才能使得起点终点都合法），枚举边就是两头的两个方案的最大值乘 $2$（注意这里一条双向边有两种走法，具体见代码），特别地，两头的方案相等的话则需要额外加一（通过这条边的时间，刚才这个贡献都在抬升的时候一起算上了，所以不用加）。

时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
#define N 400005
#define pi pair<int,int>
using namespace std;
int n,m,vis[N],a[N],u[N],v[N],ans=1e9;
vector<int>e[N],dis1,dis2;
vector<int> dij(int s){
	vector<int>dis(N);
	priority_queue<pi,vector<pi>,greater<pi> >q;
	for(int i=1;i<=n;++i)dis[i]=1e9,vis[i]=0;
	dis[s]=0;q.push({0,s});
	while(!q.empty()){
		pi c=q.top();q.pop();
		int u=c.second;
		if(vis[u])continue;
		for(int v:e[u]){
			if(max(dis[u]+1,a[v])<dis[v]){
				dis[v]=max(dis[u]+1,a[v]);
				q.push({dis[v],v});
			}
		}
	}
	return dis;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i)cin>>a[i];
	for(int i=1;i<=m;++i){
		cin>>u[i]>>v[i];
		e[u[i]].push_back(v[i]);e[v[i]].push_back(u[i]);
	}
	dis1=dij(1);dis2=dij(n);
	//for(int i=1;i<=n;++i)cout<<dis1[i]<<" ";cout<<'\n';
	//for(int i=1;i<=n;++i)cout<<dis2[i]<<" ";cout<<'\n';
	for(int i=1;i<=n;++i)ans=min(ans,2*max(dis1[i],dis2[i]));
	for(int i=1;i<=m;++i){
		int w=max(dis1[u[i]],dis2[v[i]])*2;
		if(dis1[u[i]]==dis2[v[i]])++w;
		ans=min(ans,w);
		w=max(dis2[u[i]],dis1[v[i]])*2;
		if(dis2[u[i]]==dis1[v[i]])++w;
		ans=min(ans,w); 
	}
	cout<<ans;
	return 0;
}