This is my program
program preg;
var n,m,i,t,ch,e,sh,k,shh:longint;st:boolean;s:string;des,otv:array[1..100000]of longint;b:array[1..100000]of boolean;
begin
read(n);readln(m);
sh:=1;
for i:=1 to m do begin
readln(s);
if (s[1]='L') then b[sh]:=true
else b[sh]:=false;
val(s[3],ch,e);
des[sh]:=ch;sh:=sh+1;
end;
sh:=1;
for i:=2 to m+1 do begin
  if b[i-1]=false then begin
    for k:=i to m do begin
      if des[k]>=des[i-1]then begin
      shh:=0;st:=false;
        while st=false do begin
        shh:=shh+1;st:=true;
          for t:=1 to i-1 do begin
          if (des[k]+shh=des[t])and(b[t]=false)then st:=false;
          end;
        end;
      des[k]:=des[k]+shh;
      end;
    end;
  end;
  if b[i-1]=true then begin
  otv[sh]:=des[i-1];sh:=sh+1;
  end;
end;
for i:=1 to sh-1 do writeln(otv[i]);
end.

I use balanse tree, but WA#2. here my code.
What is test#2?

import java.io.*;
import java.util.*;

public class Problem_1439 implements Runnable{
    public static void main(String []args){
        new Thread(new Problem_1439()).start();
    }
    public void run(){
        try{
            reader = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            solve();
        }catch(IOException e){
            throw new IllegalStateException(e);
        }
    }

    int nextInt()throws IOException{
        reader.nextToken();
        return (int)reader.nval;
    }

    boolean nextType()throws IOException{
        reader.nextToken();
        String s = reader.sval;
        if (s.length()!=1 && s.charAt(0)!='L' && s.charAt(0)!='D'){
            for (int i = 0; i< 100000000;i++)System.out.println("ERORO");
        }
        return reader.sval.charAt(0)=='L';
    }

    int n, m;

    StreamTokenizer reader;

    final int MAX_N = 111111;

    class node{
        int left, right;
        int lleft, rright;
        int x, y;
        int size;

        node(){
            left = right= x = y = size =  lleft = rright = 0;
        }
    }
    node tree[];
    int g[];
    int  lt, root;
    int i, j, c, k;
    int getSize(int root){
        return (root == 0 ) ? 0: tree[root].size;
    }




    int insert(int root, int x, int y){
        if (root == 0 || tree[root].y <= y){

            lt++;
            //tree[lt] = new node();
            tree[lt].left   = 0;
            tree[lt].right  = 0;
            tree[lt].lleft  = lt;
            tree[lt].rright = lt;
            tree[lt].x = x;
            tree[lt].y = y;

            if (root > 0){
                if (tree[root].x < x)tree[lt].left = root; else tree[lt].right = root;
            }
            tree[lt].size = 1 + getSize(tree[lt].left)+getSize(tree[lt].right);
            if (tree[lt].left > 0)tree[lt].lleft = tree[tree[lt].left].lleft;
            if (tree[lt].right > 0)tree[lt].rright = tree[tree[lt].right].rright;
            return lt;
        }else if (x > tree[root].x){
            tree[root].size ++;
            tree[root].right = insert(tree[root].right, x, y);
            tree[root].rright = tree[tree[root].right].rright;
            return root;
        }else {
            tree[root].size++;
            tree[root].left = insert(tree[root].left, x, y);
            tree[root].lleft = tree[tree[root].left].lleft;
            return root;
        }
    }
    int getId(int root, int k, int min){
        if (root == 0)return k + min;
        int sz = getSize(tree[root].left);
        int delta = tree[root].x - (min + sz + 1);
        //if (delta < k)return getId(tree[root].right, k, min + sz + 1);
        if (delta >= k){
            if (tree[root].left == 0)return k + min;
            int lright = tree[tree[root].left].rright;
            int delta2 = tree[lright].x - (min  + sz);
            if (delta2 < k)return k + min + sz;else return getId(tree[root].left, k, min);
        }else {
            if (tree[root].right == 0)return k + min + sz + 1;
            int rleft = tree[tree[root].right].lleft;
            int delta2 = tree[rleft].x - (min + sz + 2);
            if (delta2 >= k)return k + min + sz + 1; else return getId(tree[root].right, k , min + sz + 1);
        }
    }

    void solve()throws IOException{
        n = nextInt();
        m = nextInt();
        g = new int[ MAX_N+1];
        tree = new node[MAX_N + 1];
        for (i = 0; i<=MAX_N;i++){
            tree[i] = new node();

        }
        Random random = new Random();
        for (i = 1; i<=n;i++){
            k = 1 + random.nextInt(i);
            g[i] = g[k];
            g[k] = i;
        }
        root = 0;
        lt = 0;
        j = 0;
        int mind = n, maxd = 1, d = 0;
        boolean type;
        for (i = 1; i<= m;i++){
            type = nextType();
            k = nextInt();
            k  = getId(root, k, 0);

            if ( type ) {//L
                System.out.println(k);
            }else{//D
                j++;
                root = insert(root, k, g[j]);



            }

        }

    }
}