// #ifdef __AVX2__ // #pragma GCC target "avx2" // #endif // #pragma GCC optimize "O3" // #pragma GCC optimize "unroll-loops" #include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; // #define int long long #define elif else if #define all(l) begin(l),end(l) #define rall(l) rbegin(l),rend(l) #define append push_back #define print(l) for(auto i:l) cout<<i<<' '; cout<<endl; #define pprint(a,b) cout<<a<<' '<<b<<endl; #define inp(l) for(auto &i:l) cin>>i; // #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #define pai make_pair #define endl "\n" #define pii pair<int,int> #define fi first #define se second #define vec vector // const int mod=998244353; const int mod1=998244353; const int mod=1e9+7; const int MA=2e5+5; #define ll long long ll n; ll x[MA],y[MA]; struct node{ ll ma,mu1,li,ri; node* ch[2]; node(){ ma=0; mu1=1; ch[0]=ch[1]=NULL; } void init(int l,int r){ li=l; ri=r; } void set(int i,int v){ if(li==ri){ ma=mu1=v; return; } int m=(li+ri)/2; ma=0; mu1=1; if(i<=m){ if(ch[0]==NULL){ ch[0]=new node; ch[0]->init(li,m); } ch[0]->set(i,v); } else{ if(ch[1]==NULL){ ch[1]=new node; ch[1]->init(m+1,ri); } ch[1]->set(i,v); } if(ch[0]!=NULL){ ma=(*ch[0]).ma; mu1=(*ch[0]).mu1; } if(ch[1]!=NULL){ ma=max(ma,(*ch[1]).ma); mu1=(((*ch[1]).mu1)*mu1)%mod; } } int mx(int l,int r){ if(l<=li and ri<=r) return ma; int x=0; int m=(li+ri)/2; if(l<=m) x=ch[0]->mx(l,r); if(r>m) x=max(x,ch[1]->mx(l,r)); return x; } ll mul(int l,int r){ if(r<li or l>ri) return 1; if(l<=li and ri<=r) return mu1; ll x=1; int m=(li+ri)/2; if(l<=m) x=ch[0]->mul(l,r); if(r>m) x=(x*ch[1]->mul(l,r)); return x%mod; } }; node ry; node rx; set<pii>seg; #define int1 __int128 int ans(){ deque<pii>a; int1 tem=1; while(tem<1e9 and seg.size()){ pii b=*(seg.rbegin()); a.push_front(b); seg.erase(b); // cout<<b.fi<<endl; tem*=x[b.fi]; } // return tem; int1 ma=ry.mx(1,n); // int1 ma=1; // return tem; if(a[0].fi==0){ seg.insert(a[0]); a.pop_front(); } // return tem; tem=1; for(int i=0;i<a.size();i++){ pii b=a[i]; tem*=x[b.fi]; ma=max(ma,tem*ry.mx(b.fi,b.se)); } // return tem; for(auto i:a){ seg.insert(i); } ma%=mod; return (ma*rx.mul(1,a[0].fi-1))%mod; } int updateX(int i,int v){ i++; int pr=x[i]; x[i]=v; rx.set(i,v); if(pr>1 and v>1) return ans(); if(pr==v) return ans(); if(v==1){ auto p=seg.lower_bound(pai(i,0)); auto p1=p; p1--; pii a=*p,b=*p1; seg.erase(a); seg.erase(b); seg.insert(pai(a.fi,b.se)); } else{ auto p=seg.lower_bound(pai(i,0)); p--; pii a=*p; seg.erase(p); seg.insert(pai(a.fi,i-1)); seg.insert(pai(i,a.se)); } return ans(); } int updateY(int i,int v){ i++; ry.set(i,v); y[i]=v; return ans(); } int init(int N,int X[],int Y[]){ n=N; ry.init(0,n+5); rx.init(0,n+5); x[0]=1e9; for(int i=1;i<=n;i++){ x[i]=X[i-1]; rx.set(i,x[i]); y[i]=Y[i-1]; ry.set(i,y[i]); } int l,r; l=r=0; for(int i=1;i<=n;i++){ if(x[i]>1){ seg.insert(pai(l,r)); l=r=i; } else r++; } seg.insert(pai(l,r)); int1 tem=1; // for(auto pa:seg){ // tem*=x[pa.fi]; // cout<<x[pa.fi]<<' '<<pa.fi<<' '<<pa.se<<endl; // } // cout<<(ll)tem<<endl; return ans(); // return 0; }