LOJ_1085 - All Possible Increasing Subsequences

/* unlucky_13 Jul 22, 2013 10:21:02 PM
 *
 */
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define maxn 111111
#define mod 1000000007
#define LL  long long int
LL n ,Tree[4*maxn];
struct INT{

    LL idx,val ;
    bool operator < ( const INT& p ) const {
        if(val!=p.val) return val < p.val;
        else return idx > p.idx ;
    }
};

INT A[maxn] ;
LL query(LL n,LL s,LL e,LL i,LL j){

    if(j<s || e<i){
        return 0 ;
    }

    if(i==s && e==j){
        return Tree[n] ;
    }

    LL mid = (s+e)>>1 ;
    if(j<=mid){
        return query(2*n,s,mid,i,j) ;
    }
    else if(i>mid){
        return query(2*n+1,mid+1,e,i,j) ;
    }

    else{

       LL p1 = query(2*n,s,mid,i,mid) ;
       LL p2 = query(2*n+1,mid+1,e,mid+1,j) ;
       return (p1+p2)%mod ;
    }

}

void update(LL n,LL s,LL e,LL pos,LL val){


    if(s<=pos && pos<=e){
        Tree[n]+=val;
        Tree[n] %=mod ;
    }

    if(s==e){
        return ;
    }

    LL mid = (s+e)>>1 ;
    LL next = n<<1 ;
    if(pos<=mid){
        update(next,s,mid,pos,val) ;
    }

    else if(pos>mid){
        update(next+1,mid+1,e,pos,val) ;
    }

    else{
        update(next,s,mid,pos,val) ;
        update(next+1,mid+1,e,pos,val) ;
    }

}

int main() {

    //freopen("//home//unlucky_13//workspace//Hello_World//src//in.txt","r",stdin) ;
    LL tc,ct=0;
    scanf("%lld",&tc) ;
    while(tc!=ct){
        memset(Tree,0,sizeof(Tree)) ;
        scanf("%lld",&n) ;
        for(LL i=0;i<n;i++) {
            scanf("%lld",&A[i].val) ;
            A[i].idx = i+1 ;
        }

        sort(A,A+n) ;
        //for(LL i=0;i<n;i++) cout<<A[i].idx<<" "<<A[i].val<<endl ;
        LL res = 0 ;
        LL add = 0 ;
        //LL ADD[maxn] ;
        for(LL i=0;i<n;i++){

                   /*if(i==0 || A[i].val!=A[i-1].val) {
                       add = query(1,1,n,1,A[i].idx-1)+1 ; //to handle duplicate numbers
                   }
                   else{
                       cout<<"this"<<endl ;
                       add = add+query(1,1,n,A[i-1].idx+1,A[i].idx-1)+1 ;
                   }*/
                   add = query(1,1,n,1,A[i].idx-1)+1 ;
                   //cout<<add<<endl ;
                   add %=mod ;
                   res+=add ;
                   res %=mod ;
                   update(1,1,n,A[i].idx,add) ;

        }

        printf("Case %lld: %lld\n",++ct,res) ;

    }

    return 0;
}