#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a a; ll sign; bigint():sign(1){} bigint(ll v){ *this=v; } bigint(const string &s){ read(s); } void operator=(const bigint &v){ sign=v.sign; a=v.a; } void operator=(ll v){ sign=1; if(v<0) sign=-1,v=-v; for(;v>0;v=v/base) a.push_back(v%base); } bigint operator+(const bigint &v) const{ if(sign==v.sign){ bigint res=v; for(ll i=0,carry=0;i<(ll)max(a.size(),v.a.size())||carry;++i){ if(i==(ll)res.a.size()) res.a.push_back(0); res.a[i]+=carry+(i<(ll)a.size()?a[i]:0); carry=res.a[i]>=base; if(carry) res.a[i]-=base; } return res; } return *this -(-v); } bigint operator-(const bigint &v) const{ if(sign==v.sign){ if(abs()>=v.abs()){ bigint res=*this; for(ll i=0,carry=0;i<(ll)v.a.size()||carry;++i){ res.a[i]-=carry+(i<(ll)v.a.size()?v.a[i]:0); carry=res.a[i]<0; if(carry) res.a[i]+=base; } res.trim(); return res; } return -(v-*this); } return *this+(-v); } void operator*=(ll v){ if(v<0) sign=-sign,v=-v; for(ll i=0,carry=0;i<(ll)a.size()|| carry;++i){ if(i ==(ll)a.size()) a.push_back(0); ll cur=a[i] *(ll)v+carry; carry=(ll)(cur/base); a[i]=(ll)(cur%base); // asm("divl %%ecx" : "=a"(carry),"=d"(a[i]) : "A"(cur),"c"(base)); } trim(); } bigint operator*(ll v) const{ bigint res=*this; res *=v; return res; } friend pair divmod(const bigint &a1,const bigint &b1){ ll norm=base/(b1.a.back()+1); bigint a=a1.abs()*norm; bigint b=b1.abs()*norm; bigint q,r; q.a.resize(a.a.size()); for(ll i=a.a.size()-1;i>=0;i--){ r *=base; r+=a.a[i]; ll s1=r.a.size()<=b.a.size() ? 0 : r.a[b.a.size()]; ll s2=r.a.size()<=b.a.size()-1 ? 0 : r.a[b.a.size()-1]; ll d=((ll)base*s1+s2)/b.a.back(); r-=b*d; while(r<0) r+=b,--d; q.a[i]=d; } q.sign=a1.sign*b1.sign; r.sign=a1.sign; q.trim(); r.trim(); return make_pair(q,r/norm); } bigint operator/(const bigint &v) const{ return divmod(*this,v).first; } bigint operator%(const bigint &v) const{ return divmod(*this,v).second; } void operator/=(ll v){ if(v<0) sign=-sign,v=-v; for(ll i=(ll)a.size()-1,rem=0;i>=0;--i){ ll cur=a[i]+rem *(ll)base; a[i]=(ll)(cur/v); rem=(ll)(cur%v); } trim(); } bigint operator/(ll v) const{ bigint res=*this; res/=v; return res; } ll operator%(ll v) const{ if(v<0) v=-v; ll m=0; for(ll i=a.size()-1;i>=0;--i) m=(a[i]+m *(ll)base)%v; return m*sign; } void operator+=(const bigint &v){ *this=*this+v; } void operator-=(const bigint &v){ *this=*this-v; } void operator*=(const bigint &v){ *this=*this*v; } void operator/=(const bigint &v){ *this=*this/v; } bool operator<(const bigint &v) const{ if(sign!=v.sign) return sign=0;i--) if(a[i]!=v.a[i]) return a[i]*sign(const bigint &v) const{ return v<*this; } bool operator<=(const bigint &v) const{ return !(v<*this); } bool operator>=(const bigint &v) const{ return !(*this=0;i--) res=res*base+a[i]; return res*sign; } friend bigint gcd(const bigint &a,const bigint &b){ return b.isZero() ? a : gcd(b,a%b); } friend bigint lcm(const bigint &a,const bigint &b){ return a/gcd(a,b)*b; } void read(const string &s){ sign=1; a.clear(); ll pos=0; while(pos<(ll)s.size()&&(s[pos]=='-'|| s[pos]=='+')){ if(s[pos]=='-') sign=-sign; ++pos; } for(ll i=s.size()-1;i>=pos;i-=base_digits){ ll x=0; for(ll j=max(pos,i-base_digits+1);j<=i;j++) x=x*10+s[j]-'0'; a.push_back(x); } trim(); } friend istream &operator>>(istream &stream,bigint &v){ string s; stream>>s; v.read(s); return stream; } friend ostream &operator<<(ostream &stream,const bigint &v){ if(v.sign==-1) stream<<'-'; stream<<(v.a.empty() ? 0 : v.a.back()); for(ll i=(ll)v.a.size()-2;i>=0;--i) stream< convert_base(const vector &a, ll old_digits,ll new_digits){ vector p(max(old_digits,new_digits)+1); p[0]=1; for(ll i=1;i<(ll)p.size();i++) p[i]=p[i-1]*10; vectorres; ll cur=0; ll cur_digits=0; for(ll i=0;i<(ll)a.size();i++){ cur+=a[i]*p[cur_digits]; cur_digits+=old_digits; while(cur_digits>=new_digits){ res.push_back(signed(cur%p[new_digits])); cur/=p[new_digits]; cur_digits-=new_digits; } } res.push_back((signed)cur); while(!res.empty()&&!res.back()) res.pop_back(); return res; } typedef vector vll; static vll karatsubaMultiply(const vll &a,const vll &b){ ll n=a.size(); vll res(n+n); if(n<=32){ for(ll i=0;i>1; vll a1(a.begin(),a.begin()+k); vll a2(a.begin()+k,a.end()); vll b1(b.begin(),b.begin()+k); vll b2(b.begin()+k,b.end()); vll a1b1=karatsubaMultiply(a1,b1); vll a2b2=karatsubaMultiply(a2,b2); for(ll i=0;ia6=convert_base(this->a,base_digits,6); vectorb6=convert_base(v.a,base_digits,6); vll a(a6.begin(),a6.end()); vll b(b6.begin(),b6.end()); while(a.size() struct BIT{ int n; vector bit; //1-indexed BIT():n(-1){} BIT(int n_,T d):n(n_),bit(n_+1,d){} T sum(int i){ T s=bit[0]; for(int x=i+1;x>0;x-=(x&-x)) s+=bit[x]; return s; } void add(int i,T a){ if(i==0) return; for(int x=i+1;x<=n;x+=(x&-x)) bit[x]+=a; } }; //INSERT ABOVE HERE const int MAX = 1e5+100; int dp[MAX]; pair dfs(int l,int r){ if(l+1>=r) return make_pair(bigint(dp[l]),bigint(l+1)); int m=(l+r)>>1; auto v=dfs(l,m); auto t=dfs(m,r); t.first*=v.second; t.first+=v.first; t.second*=v.second; return t; } signed main(){ int n; cin>>n; vector p(n); for(int i=0;i>p[i]; BIT bit(n+1,0); for(int i=0;i