#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int tr[N<<2],lazy[N<<2],a[N];
struct Node {
	int l,r;
}q[N];
int midans,n,m;
void Push_Down(int p,int l,int r) {
	if (lazy[p]==-1||l==r)return;
	int mid = (l+r)>>1;
	tr[p<<1] = (mid-l+1)*lazy[p];
	tr[p<<1|1] = (r-mid)*lazy[p];
	lazy[p<<1] = lazy[p<<1|1] = lazy[p];
	lazy[p] = -1;
}
void Build(int p,int l,int r) {
	lazy[p] = -1;
	if (l==r) {
		tr[p] = a[l] > midans;
		return;
	}
	int mid = (l+r)>>1;
	Build(p<<1,l,mid);
	Build(p<<1|1,mid+1,r);
	tr[p] = tr[p<<1]+tr[p<<1|1];
}
void Update(int p,int l,int r,int a,int b,int c) {
	if (a > b) return;
	Push_Down(p,l,r);
	if (l >= a && r <= b) {
		tr[p] = (r-l+1)*c;
		lazy[p] = c;
		return;
	}
	int mid = (l+r)>>1;
	if (a <= mid) Update(p<<1,l,mid,a,b,c);
	if (b > mid) Update(p<<1|1,mid+1,r,a,b,c);
	tr[p] = tr[p<<1] + tr[p<<1|1];
}
int Getans(int p,int l,int r,int a,int b) {
	Push_Down(p,l,r);
	if (l >= a && r <= b) return tr[p];
	int ans = 0;
	int mid = (l+r)>>1;
	if (a <= mid) ans+= Getans(p<<1,l,mid,a,b);
	if (b > mid) ans+= Getans(p<<1|1,mid+1,r,a,b);
	return ans;
}
bool check(int x) {
	midans = x;
	Build(1,1,n);
	for (int i = 1;i<= m;i++) {
		int L = min(q[i].l,q[i].r);
		int R = max(q[i].l,q[i].r);
		int tmp = Getans(1,1,n,L,R);
		if (q[i].l < q[i].r) {
			Update(1,1,n,L,R-tmp,0);
			Update(1,1,n,R-tmp+1,R,1);
		} else {
			Update(1,1,n,L,L+tmp-1,1);
			Update(1,1,n,L+tmp,R,0);
		}
	}
	int midpos = (n>>1)+1;
	int t = Getans(1,1,n,midpos,midpos);
	return t == 1;
}
int GetFinalans() {
	int l = 1,r = n+1;
	while (l < r) {
		int mid = (l+r)>>1;
		if (check(mid))l = mid+1;
		else r = mid;
	}
	return l;
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i = 1;i<= n;i++)scanf("%d",&a[i]);
	for (int i = 1;i<= m;i++)
		scanf("%d%d",&q[i].l,&q[i].r);
	printf("%d\n",GetFinalans());
	return 0;
}