#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
llo mod=1e9+7;
llo n;
llo it[200001];
pair<llo,llo> dp[200001];
pair<llo,llo> dp2[200001];
llo pre[200001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(llo i=0;i<n;i++){
cin>>it[i];
}
for(llo i=0;i<n/2;i++){
swap(it[i],it[n-i-1]);
}
pre[0]=1;
for(llo i=1;i<=n;i++){
pre[i]=(pre[i-1]*2)%mod;
}
dp[0]={1,1};
vector<vector<pair<llo,llo>>> ss;
ss.pb({{it[0],1}});
for(llo i=1;i<n;i++){
int ind=-1;
if(it[i]>ss.back().back().a){
ind=ss.size()-1;
int low=0;
int high=ss[ind].size()-1;
while(low<high-1){
int mid=(low+high)/2;
if(ss[ind][mid].a<it[i]){
high=mid;
}
else{
low=mid;
}
}
int ind2=high;
if(ss[ind][low].a<it[i]){
ind2=min(ind2,low);
}
int co=ss[ind].back().b;
if(ind2>0){
co=(co-ss[ind][ind2-1].b+mod)%mod;
}
dp[i]={ss.size()+1,co};
ss.pb({{it[i],dp[i].b}});
}
else if(it[i]<=ss[0].back().a){
dp[i]={1,1};
ss[0].pb({it[i],(ss[0].back().b+dp[i].b)%mod});
}
else{
int low=0;
int high=ss.size()-2;
while(low<high-1){
int mid=(low+high)/2;
if(ss[mid].back().a<it[i]){
low=mid;
}
else{
high=mid;
}
}
int ind=low;
if(ss[high].back().a<it[i]){
ind=max(ind,high);
}
low=0;
high=ss[ind].size()-1;
while(low<high-1){
int mid=(low+high)/2;
if(ss[ind][mid].a<it[i]){
high=mid;
}
else{
low=mid;
}
}
int ind2=high;
if(ss[ind][low].a<it[i]){
ind2=min(ind2,low);
}
int co=ss[ind].back().b;
if(ind2>0){
co=(co-ss[ind][ind2-1].b+mod)%mod;
}
dp[i]={ind+2,co};
ss[ind+1].pb({it[i],(ss[ind+1].back().b+dp[i].b)%mod});
// ss.pb({{it[i],dp[i].b}});
}
/* llo ma=0;
for(llo j=0;j<i;j++){
if(it[j]<it[i]){
ma=max(ma,dp[j].a);
}
}
if(ma==0){
dp[i]={1,1};
}
else{
dp[i]={ma+1,0};
for(llo j=0;j<i;j++){
if(it[j]<it[i]){
if(dp[j].a==ma){
dp[i].b=(dp[i].b+dp[j].b)%mod;
}
}
}
}*/
}
dp2[0]={1,1};
for(llo i=0;i<n;i++){
it[i]=-it[i];
llo ma=0;
for(llo j=0;j<i;j++){
if(it[j]<it[i]){
ma=max(ma,dp2[j].a);
}
}
if(ma==0){
dp2[i]={1,1};
}
else{
dp2[i]={ma+1,0};
for(llo j=0;j<i;j++){
if(it[j]<it[i]){
if(dp2[j].a==ma){
dp2[i].b=(dp2[i].b+dp2[j].b)%mod;
}
}
}
}
}
for(llo i=0;i<n/2;i++){
swap(dp[i],dp[n-i-1]);
}
for(llo i=0;i<n/2;i++){
swap(dp2[i],dp2[n-i-1]);
}
/* for(llo i=0;i<n;i++){
cout<<dp[i].a<<":"<<dp[i].b<<endl;
}
cout<<endl;
for(llo i=0;i<n;i++){
cout<<dp2[i].a<<":"<<dp2[i].b<<endl;
}
cout<<endl;*/
llo ans=0;
llo ma=0;
for(llo i=0;i<n;i++){
ma=max(ma,dp[i].a+dp2[i].a-1);
}
for(llo i=0;i<n;i++){
if(dp[i].a+dp2[i].a-1==ma){
llo ans2=(dp[i].b*dp2[i].b)%mod;
ans2=(ans2*pre[n-ma])%mod;
/*if(i>0){
ans2=(ans2*2)%mod;
}*/
ans=(ans2+ans)%mod;
//cout<<ans2<<":";
}
}
cout<<ma<<" "<<ans<<endl;
/* vector<vector<pair<llo,llo>>> ss;
ss.pb({{-it[i],1}});
vector<vector<pair<llo,llo>>> tt;
tt.pb({{it[i],1}});
for(llo i=1;i<n;i++){
if(it[i]==it[0]){
continue;
}
llo xx=it[i];
else if(it[i]<it[0]){
}
else{
if(xx<=tt[0].back().a){
}
if(xx>tt[tt.size()-1].back().a){
tt
}
}
}*/
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Execution timed out |
1098 ms |
9068 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1092 ms |
8436 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1090 ms |
7404 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1092 ms |
8316 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1075 ms |
10488 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1070 ms |
11996 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1093 ms |
14368 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1096 ms |
14240 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1053 ms |
14216 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1060 ms |
14380 KB |
Time limit exceeded |
