【图论，思维】
题意简述
有个天平，两边相差1g的时候还是平的，相差1g以上就会倾斜。

你有一盒1g的砝码，每个砝码标记为1~N

你要按照1~N的顺序把砝码放到天平上去（自由选择放左边还是右边），再按照a[i]数组的顺序把砝码拿下来。

整个过程中天平不可以倾斜。

为了达成上述条件，
问你放上去的时候，每一个砝码放左边还是右边，用类似：LRLRLRL来表示。

保证有解，而且输出一种可行解即可。

Problem
You have a special balance scale, with two pans (left and right) that are both initially empty. You also have a box of identical 1-gram marbles. There are N of these marbles, and the marbles are numbered from 1 to N.

Your scale is very sensitive, and you know that if the total weight on the left pan and the total weight on the right pan ever differ by strictly more than 1 gram, the scale will break. For example, if at some point there are 4 marbles in one of the pans, there must be either 3, 4, or 5 marbles in the other pan.

Your friend Libra has challenged you to do the following, without breaking the scale at any point:
First, put all of the marbles on the scale one at a time, in numerical order: marble 1, then marble 2, and so on up to marble N. For each marble, you choose whether to place it on the left pan or on the right pan.
Then, remove all of the marbles from the scale one at a time, in an order A1, A2, …, AN specified by your friend. This order is a permutation of 1, 2, …, N. The i-th marble you remove must be the marble numbered Ai.

Can you find a way to do this?

Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with one line with an integer N: the number of marbles. Then, there is one more line with N integers A1, A2, …, AN, which constitute a permutation of the first N natural numbers. The marble numbered Ai must be the i-th marble that you remove in the removal phase.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a string of N characters. The i-th of these characters (counting starting from 1) should be uppercase L if the i-th numbered marble should be put on the left pan, or uppercase R if it should be put on the right pan.

It is guaranteed that at least one answer exists. If there are multiple valid answers, you may output any one of them.

Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Ai ≤ N, for all i.
Ai ≠ Aj for all i ≠ j.

Test set 1 (Visible Verdict)
2 ≤ N ≤ 16.
N is even.

Test set 2 (Hidden Verdict)
2 ≤ N ≤ 1000.
N is even.

Test set 3 (Hidden Verdict)
1 ≤ N ≤ 1000.

Sample

Input

2
4
3 1 2 4
4
1 2 3 4

Output

Case #1: LRRL
Case #2: LRLR

In Sample Case #1, we will put marble 1 on the left pan, then put marble 2 on the right pan, then put marble 3 on the right pan, then put marble 4 on the left pan. Notice that the total weights on the left and right pans — (1, 0), (1, 1), (1, 2), and (2, 2) — never differ by more than 1 throughout this process.

Then, we must remove the marbles in the order 3, 1, 2, 4. Again, the total weights on the left and right pans — (2, 1), (1, 1), (1, 0), (0, 0) — never differ by more than 1 at any point. We have succeeded!

Also notice that RLLR would be a valid answer for this case, per the same reasoning above (but with the two pans swapped).

Notice that the following are examples of invalid answers for this case:
LLRR: breaks the scale when placing marble 2
LRLR: breaks the scale when removing marble 1 (which is the second marble to be removed)

Although there are no samples with odd N (since that is only possible in Test Set 3), here are some examples:
1: Either L or R would be acceptable.
2 3 1: LRR and RLL are the only acceptable answers. LLL, LLR, RRL, and RRR would break the scale during the placement phase. LRL and RLR would break the scale during the removal phase.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

const int N=2020;
int h[N],e[N],ne[N],idx;
int n;
int a[N];
char s[N];
bool st[N];


void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
char getneg(char d){
    if(d=='L') return 'R';
    else return 'L';
}

void bfs(int x){
    queue<int> q;
    s[x]='L';
    q.push(x);
    st[x]=true;

    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(!st[j]){
                s[j]=getneg(s[t]);
                q.push(j);
                st[j]=true;
            }
        }
    }


}
int main(){

    int T,casei=0;
    cin>>T;
    while(T--){
        //初始化
        idx=1;
        memset(h,-1,sizeof h);
        memset(st,0,sizeof st);
        casei++;
        cin>>n;

        //连边
        for(int i=1;i<=n;i++) {
            cin>>a[i];
            if(i%2==0){
                add(i,i-1);
                add(i-1,i);
            }
        }
        for(int i=n;i>0;i-=2){
            add(a[i],a[i-1]);
            add(a[i-1],a[i]);
        }

        for(int i=1;i<=n;i++){
            if(st[i]==false){
                bfs(i);
            }
        }


        cout<<"Case #"<<casei<<": ";
        for(int i=1;i<=n;i++){
            cout<<s[i];
        }
        cout<<endl;

    }
    return 0;
}