Recently yifenfei face such a problem that give you millions of positive integers,tell how many pairs i and j that satisfy F[i] smaller than F[j] strictly when i is smaller than j strictly. i and j is the serial number in the interger sequence. Of course, the problem is not over, the initial interger sequence will change all the time. Changing format is like this [S E] (abs(E-S)<=1000) that mean between the S and E of the sequece will Rotate one times. 

For example initial sequence is 1 2 3 4 5. 

If changing format is [1 3], than the sequence will be 1 3 4 2 5 because the first sequence is base from 0. 

InputThe input contains multiple test cases. 

Each case first given a integer n standing the length of integer sequence (2<=n<=3000000) 

Second a line with n integers standing F[i](0<F[i]<=10000) 

Third a line with one integer m (m < 10000) 

Than m lines quiry, first give the type of quiry. A character C, if C is ‘R’ than give the changing format, if C equal to ‘Q’, just put the numbers of satisfy pairs. 

OutputOutput just according to said.Sample Input

51 2 3 4 53QR 1 3Q

Sample Output

108

题解

这道题我们可以用树状数组求出原数组的答案

因为abs(E-S)<=1000，m<10000，所以我们可以枚举每次的区间，因为翻转每次是S+1~E往前移一位，第S个到E

所以我们先把第S位存下来，每次和后面的判断一下大小就可以了

当输入是Q的时候就直接输出就可以了

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
            5 #define ll long long 6 #define M 10005 7 #define N 3000005 8 using namespace std; 9 int n,m,x,y;10 ll ans;11 int a[N];12 ll tr[M];13 char s[10];14 int lowbit(int x){ return x&(-x); }15 void add(int x){16     while (x<=M){17         tr[x]++;18         x+=lowbit(x);19     }20 }21 int query(int x){22     int s=0;23     while (x>0){24         s+=tr[x];25         x-=lowbit(x);26     }27     return s;28 }29 int main(){30     while (~scanf("%d",&n)){31         memset(tr,0,sizeof(tr)); ans=0;32         for (int i=0;i
          
           a[i]) ans++;48                 }49                 a[y]=s;50             }51         }52     }53     return 0;54 }