Aimeeeee

把原图改造一下$>=mid$那么权值为1，反之为0

然后跑最长路，如果最长路不小于0，那么就可行，反之不行

#include
#include
#include
#include
#include
#define int long long
using namespace std;
int n,m;
long long Aimee[1000001];
int x,y;
queue q;
struct b{
    int to;
    int ne;
} ed[1000001];
int Ai;
int head[1000001];
int vis[1000001];
int dp[1000001];
int tem[1000001];
void add(int f,int to){
    Ai++;
    ed[Ai].to=to;
    ed[Ai].ne=head[f];
    head[f]=Ai;
    return ;
}
long long l,r;
int dfs(int no,int k){
    if(vis[no])
    return dp[no];
    vis[no]=1;
    for(int i=head[no];i;i=ed[i].ne){
        dp[no]=max(dp[no],dfs(ed[i].to,k)+tem[ed[i].to]);
    }
    return dp[no];
}
bool check(int now){
    for(int i=0;i<=n;++i){
        tem[i]=(Aimee[i]>=now? 1 :-1);
        vis[i]=0;
        dp[i]=-999999999;
    }
        dp[n]=0;
        vis[n]=1;
    dfs(1,now);
    dp[1]+=tem[1];
    return dp[1]>=0;
}
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%lld",&Aimee[i]);
    }
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        add(x,y); 
    }
    int ans;
    ans=r=9999999990;

    while(l<=r){
        long long mid=l+(r-l)/2;
        if(check(mid)){
            l=mid+1;
            ans=mid;
        }else{
            r=mid-1;
        }
    }
    cout<<(ans==(long long)9999999990?-1 :ans);
    return 0;
}