#include <bits/stdc++.h>
#define int long long
#define REP(v, i, j) for (int v = i; v != j; v++)
#define FORI(v) for (auto i : v)
#define FORJ(v) for (auto j : v)
#define OUT(v, a) \
FORI(v) \
cout << i << a;
#define OUTS(v, a, b) \
cout << v.size() << a; \
OUT(v, b)
#define in(a, n) \
REP(i, 0, n) \
cin >> a[i];
#define SORT(v) sort(begin(v), end(v))
#define REV(v) reverse(begin(v), end(v))
#define MEMSET(m) memset(m, -1, sizeof m)
#define pb push_back
#define fi first
#define se second
#define detachIO \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
using namespace std;
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
bool operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
if(__x.size() != __y.size()) return false;
return std::equal(__x.begin(), __x.end(), __y.begin());
}
typedef pair<long long, long long> pii;
typedef pair<pii, long long> piii;
typedef pair<pii, pii> piiii;
int d1[200100];
int d2[200100];
int o1[200100];
int o2[200100];
vector<int> adj[200100];
int h[200100];
signed main(){
int n;cin>>n;
int m;cin>>m;
REP(i,0,n){
cin>>h[i];
}
REP(i,0,n+20)d1[i]=2e18,d2[i]=2e18;
REP(i,0,m){
int x,y;cin>>x>>y;x--,y--;
adj[x].pb(y);
adj[y].pb(x);
}
priority_queue<pii,vector<pii>,greater<pii>> pq;
set<int> vis;
pq.push({0,0});
while(pq.size()){
auto top=pq.top();
pq.pop();
if(vis.count(top.se))continue;
vis.insert(top.se);
if(top.fi>d1[top.se])continue;
d1[top.se]=top.fi;
o1[top.se]=max(o1[top.se],h[top.se]);
FORI(adj[top.se]){
int t=max(top.fi+1,h[i]);
if(d1[i]>t)d1[i]=t,o1[i]=max(o1[top.se],h[i]);
if(d1[i]==t)d1[i]=t,o1[i]=min(o1[i],max(o1[top.se],h[i]));
pq.push({t,i});
}
}
pq.push({0,n-1});
vis.clear();
while(pq.size()){
auto top=pq.top();
pq.pop();
if(vis.count(top.se))continue;
vis.insert(top.se);
if(top.fi>d2[top.se])continue;
d2[top.se]=top.fi;
o2[top.se]=max(o2[top.se],h[top.se]);
FORI(adj[top.se]){
int t=max(top.fi+1,h[i]);
if(d2[i]>t)d2[i]=t,o2[i]=max(o2[top.se],h[i]);
if(d2[i]==t)d2[i]=t,o2[i]=min(o2[i],max(o2[top.se],h[i]));
pq.push({t,i});
}
}
int ans=3e18;
REP(i,0,n){
if(o1[i]==h[i] && o2[i]==h[i])ans=min(ans,d1[i]+d2[i]);
}
// REP(i,0,n)cerr<<o1[i]<<" ";
// cerr<<endl;
// REP(i,0,n)cerr<<h[i]<<" ";
// cerr<<endl;
// REP(i,0,n)cerr<<o2[i]<<" ";
// cerr<<endl;
// REP(i,0,n)cerr<<d1[i]<<" ";
// cerr<<endl;
// REP(i,0,n)cerr<<d2[i]<<" ";
// cerr<<endl;
cout<<ans<<'\n';
}
