AMR11H

AMR11H

#include<iostream>
using namespace std;
const int MAX=1000000007;
int power(int n,int m)
{
    int i,result=1;
    for(i=0;i<m;i++) result=result*n%MAX;
    return result;
}

int main()
{
int min_count,max_count,substr,min,max,a,b,i,j,t,n,temp;
int pos_min[100000],pos_max[100000];
long long int subseq;
cin>>t;
while(t--)
{
    min=100001;max=0;min_count=max_count=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        scanf("%d",&temp);
        if(min>temp){min=temp;min_count=1;pos_min[min_count-1]=i;}
        else if(min==temp) {min_count++;pos_min[min_count-1]=i;}
       
        if(max<temp){max=temp;max_count=1;pos_max[max_count-1]=i;}
        else if(max==temp) {max_count++;pos_max[max_count-1]=i;}
    }
    if(min==max) subseq=power(2,n)-1;//(2^N-1)
    else subseq=(long long)(power(2,min_count)-1)*(power(2,max_count)-1)%MAX*power(2,n-min_count-max_count)%MAX;

    if(pos_min[min_count-1]<pos_max[max_count-1]) temp=pos_min[min_count-1];
    else temp=pos_max[max_count-1];
   
    for(substr=a=b=i=0;i<=temp;i++)
    {
        while(pos_min[a]<i)a++;
        j=pos_min[a];
        while(pos_max[b]<i)b++;
        if(pos_max[b]>j) j=pos_max[b];
        substr=(substr+n-j)%MAX;
}
        printf("%d %lld\n",substr,subseq);
}
return 0;
}