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.

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.

The 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.

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.

提交代码