#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define Tree int h,int l,int r
#define left 2*h,l,(l+r)/2
#define right 2*h+1,(l+r)/2+1,r
#define Pb push_back
#define Mp make_pair
#define F first
#define S second
long long inf=2000000008;
long long Mod=1000000007;
int n,x[500002],y[500002],ANS;
int v[2000002];
int V[2000002];
int Suf[2000002];
int Pre[2000002];
int L,R;
int Pro(Tree)
{
if (L>r || l>R) return 1;
if (L<=l && r<=R) return v[h];
return (1LL*Pro(left)*Pro(right))%Mod;
}
void UpPro(Tree)
{
if (l>L || r<L) return ;
if (L==l && r==L) { v[h]=R%Mod; return ; }
UpPro(left);
UpPro(right);
v[h]=(1LL*v[2*h]*v[2*h+1])%Mod;
}
void Upd(Tree)
{
if (L>r || L<l) return ;
if (L==l && L==r)
{
V[h]=L;
Pre[h]=R;
Suf[h]=1;
return ;
}
Upd(left);
Upd(right);
if (y[V[2*h]]<1LL*min(inf,1LL*Suf[2*h]*Pre[2*h+1])*y[V[2*h+1]])
{
V[h]=V[2*h+1];
Pre[h]=min(min(1LL*Pre[2*h]*Suf[2*h],inf)*Pre[2*h+1],inf);
Suf[h]=Suf[2*h+1];
}
else
{
V[h]=V[2*h];
Pre[h]=Pre[2*h];
Suf[h]=min(min(1LL*Pre[2*h+1]*Suf[2*h+1],inf)*Suf[2*h],inf);
}
}
pair < int , pair < int , int > > Get(Tree)
{
if (L>r || l>R) return Mp(0,Mp(1,1));
if (L<=l && r<=R) return Mp(V[h],Mp(Pre[h],Suf[h]));
pair < int , pair < int , int > > X1=Get(left);
pair < int , pair < int , int > > X2=Get(right);
if (y[X1.F]<min(1LL*y[X2.F]*min(1LL*X2.S.F*X1.S.S,inf),inf))
return Mp(X2.F,Mp(min(1LL*min(1LL*X1.S.F*X1.S.S,inf)*X2.S.F,inf),X2.S.S));
if (y[X1.F]>=min(1LL*y[X2.F]*min(1LL*X2.S.F*X1.S.S,inf),inf))
return Mp(X1.F,Mp(X1.S.F,min(1LL*min(1LL*X2.S.F*X2.S.S,inf)*X1.S.S,inf)));
}
int init(int N, int X[], int Y[]) {
n=N;
for (int i=1; i<=n; i++)
x[i]=X[i-1],y[i]=Y[i-1];
for (int i=1; i<=n; i++) {
L=i; R=x[i];
Upd(1,1,n);
UpPro(1,1,n);
}
L=1; R=n;
R=Get(1,1,n).F; L=1;
return (1LL*Pro(1,1,n)*y[R])%Mod;
}
int updateX(int pos, int val) {
pos++;
L=pos; R=val;
x[pos]=val;
Upd(1,1,n);
UpPro(1,1,n);
L=1; R=n;
R=Get(1,1,n).F; L=1;
return (1LL*Pro(1,1,n)*y[R])%Mod;
}
int updateY(int pos, int val) {
pos++;
L=pos; R=x[pos];
y[pos]=val;
Upd(1,1,n);
L=1; R=n;
R=Get(1,1,n).F; L=1;
return (1LL*Pro(1,1,n)*y[R])%Mod;
}
