#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10,mod=1e9+7;
long long mypow(long long m,long long y){
if(y==0){
return 1;
}
long long p=mypow(m,(y>>1));
p*=p;
p%=mod;
if(y&1){
p*=m;
p%=mod;
}
return p;
}
long long n,all[maxn],len[maxn],dp[maxn];
struct node{
int mx,ted;
node(){
mx=0;
ted=1;
}
}fakenode;
int kaf=(1<<18);
struct segment{
node seg[(1<<19)];
node merge(node a,node b){
if(a.mx>b.mx){
return a;
}else if(b.mx>a.mx){
return b;
}
a.ted+=b.ted;
a.ted%=mod;
if(a.mx==0){
a.ted=1;
}
return a;
}
void upd(int i,int l,int r,int tl,int tr,node f){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
seg[i]=merge(f,seg[i]);
return ;
}
int m=(l+r)>>1;
upd((i<<1),l,m,tl,tr,f);
upd((i<<1)^1,m+1,r,tl,tr,f);
seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
}
node pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return fakenode;
}
if(l>=tl&&r<=tr){
return seg[i];
}
int m=(l+r)>>1;
return merge(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
}
}seginc,segdec;
void vorod(){
cin>>n;
vector<int>allind;
for(long long i=0;i<n;i++){
cin>>all[i];
allind.push_back(all[i]);
}
sort(allind.begin(),allind.end());
allind.resize(unique(allind.begin(),allind.end())-allind.begin());
for(int i=0;i<n;i++){
all[i]=lower_bound(allind.begin(),allind.end(),all[i])-allind.begin();
}
}
void solve(){
for(int i=n-1;i>=0;i--){
node fdec=segdec.pors(1,0,kaf-1,all[i]+1,n+1);
node finc=seginc.pors(1,0,kaf-1,0,all[i]-1);
len[i]=fdec.mx+finc.mx+1;
dp[i]=1ll*fdec.ted*finc.ted%mod;
//cout<<i<<" "<<finc.mx<<" "<<finc.ted<<" "<<fdec.mx<<" "<<fdec.ted<<endl;
finc.mx++;
fdec.mx++;
if(finc.mx==1){
finc.ted=1;
}
if(fdec.mx==1){
fdec.ted=1;
}
seginc.upd(1,0,kaf-1,all[i],all[i],finc);
segdec.upd(1,0,kaf-1,all[i],all[i],fdec);
}
}
void khor(){
long long ted=0,res=0;
for(int i=0;i<n;i++){
if(len[i]==res){
ted+=dp[i];
ted%=mod;
}else if(len[i]>res){
res=len[i];
ted=dp[i];
}
}
//cout<<"wtf: "<<res<<" "<<ted<<endl;
ted=1ll*ted*mypow(2,n-res)%mod;
cout<<res<<" "<<ted<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("inp.txt","r",stdin);
vorod();
solve();
khor();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12888 KB |
Output is correct |
| 5 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 6 |
Correct |
3 ms |
12924 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 9 |
Correct |
3 ms |
12936 KB |
Output is correct |
| 10 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 11 |
Correct |
155 ms |
14176 KB |
Output is correct |
| 12 |
Correct |
124 ms |
14096 KB |
Output is correct |
| 13 |
Correct |
119 ms |
14044 KB |
Output is correct |
| 14 |
Correct |
166 ms |
14144 KB |
Output is correct |
| 15 |
Correct |
230 ms |
14900 KB |
Output is correct |
| 16 |
Correct |
238 ms |
15304 KB |
Output is correct |
| 17 |
Correct |
180 ms |
14500 KB |
Output is correct |
| 18 |
Correct |
201 ms |
14524 KB |
Output is correct |
| 19 |
Correct |
193 ms |
14744 KB |
Output is correct |
| 20 |
Correct |
204 ms |
14732 KB |
Output is correct |
