Turing Hut X Avengers

Author : shailesh_2004

Required Knowledge :Combinatorics, Binary Exponentation, Segment Trees

Time Complexity : $\mathcal{O}(N + D)$

Editorialist : shailesh_2004

Approach:

Fix the minimum element and try to find the number of subsequences.

Let the fixed minimum element be at $i^{th}$ index, and $j$ is an index right side to $i$ $(j \gt i)$ such that $a_j \geq a_i$, let $cnt$ be the number of elements in between $i^{th}$ and $j^{th}$ index that are less than $a_i$, then the total number of subsequences with $i^{th}$ and $j^{th}$ elements as extremites are $2^{cnt}$, but we also added a case where the elements of the subsequence are only $a_i$ and $a_j$, but the size should be atleast $3$, so remove this and add $2^{cnt} - 1$ to answer.

Similarly, take $j$ as index left side to $i$ $(j \lt i)$ such that $a_j \gt a_i$ (We are not taking $a_j \geq a_i$ because equal to case is already included in the above), let $cnt$ be the number of elements in between $j^{th}$ and $i^{th}$ index that are less than $a_i$, then the total number of subsequences with $j^{th}$ and $i^{th}$ elements as extremites are $2^{cnt}$, but we also added a case where the elements of the subsequence are only $a_j$ and $a_i$, but the size should be atleast $3$, so remove this and add $2^{cnt} - 1$ to answer.

While computing $2^{cnt}$, use binary exponentation.

Note: This can also be solved using Segment Trees.

Setter's Code:

// Author : Shailesh
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define endl "\n"
#define mod 1000000007
#define tot(a) a.begin(),a.end()
#define minii *min_element
#define maxii *max_element
  
ll binexp(ll a,ll b,ll mod2=mod)
{
    ll res=1;
    a%=mod2;
    while(b)
    {
        if(b%2)res=(res*a)%mod2;
        a=(a*a)%mod2;
        b>>=1;
    }
    return res;
}
  
void solve()
{
    ll n;
    cin>>n;
    ll a[n+1],i;
    for(i=1;i<=n;i++)cin>>a[i];
    ll j,cnt;
    ll ans=0;
    for(i=1;i<=n;i++)
    {
        cnt=0;
        for(j=i+1;j<=n;j++)
        {
            if(a[j]>=a[i])
            {
                ans=(ans+binexp(2,cnt)-1)%mod;
            }
            if(a[j]<a[i])
            {
                cnt++;
            }
        }
        cnt=0;
        for(j=i-1;j>=1;j--)
        {
            if(a[j]>a[i])
            {
                ans=(ans+binexp(2,cnt)-1)%mod;
            }
            if(a[j]<a[i])
            {
                cnt++;
            }
        }
    }
    cout<<ans<<endl;
}
 
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    ll t;cin>>t;while(t--)
    solve();
    return 0;
}