Apostek Java Hiring Challenge

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Iterator;

import java.util.Scanner;

import java.util.Set;

import java.util.TreeMap;

import java.util.TreeSet;

public class apostek {

static class index{

public long a,b;

public index(long a,long b){

this.a=a;

this.b=b;

}

@Override

public String toString() {

return "index [a=" + a + ", b=" + b + "]";

}

}

public static void insertSort(ArrayList<index> arr) {

int n = arr.size();

        for (int i=arr.size()-1; i<n; ++i)

        {

            index key = arr.get(i);

            int j = i-1;

            while (j>=0 && ( (arr.get(j).b-arr.get(j).a) > (key.b-key.a) || ((arr.get(j).b-arr.get(j).a) == (key.b-key.a) && arr.get(j).a<key.a)))

            {

                arr.add(j+1, arr.get(j));

                arr.remove(j+2);

                j = j-1;

            }

//            while(j>=0 && ((arr.get(j).b-arr.get(j).a) == (key.b-key.a) && arr.get(j).a<key.a))

//            {

//             arr.add(j+1, arr.get(j));

//                 arr.remove(j+2);

//                 j = j-1;

//            }

            arr.add(j+1, key);

            arr.remove(j+2);

        }

}

public static void main(String args[]) {

Scanner sc = new Scanner(System.in);

long n,k;

String str;

n=sc.nextLong();

k=sc.nextLong();

sc.nextLine();

str=sc.nextLine();

int q;

// sc.nextInt()

q=sc.nextInt();

// sc.next();

ArrayList<index> arr =new ArrayList<index>();

arr.add(new index(1,n));

int i=0;

int Q=(int) k;

TreeMap<Long,Long> res = new TreeMap<Long, Long>();

while(Q-->0) {

// for(int w=0;w<arr.size();w++)

// System.out.println("array print "+arr.get(w));

index ind = arr.get(arr.size()-1);

// System.out.println("comming op "+ind);

index left = new index(0,0),right=new index(0,0);

arr.remove(ind);

long a,b,c;

// even

if((ind.a+ind.b)%2==1) {

c=(ind.a+ind.b)/2;

char t = str.charAt(i);

if(t=='L') {

res.put(c, (long) (i+1) );

if(c-1>=ind.a) {

left.a = ind.a;

left.b = c-1; 

} else left=null;

if(c+1<=ind.b) {

right.a = c+1;

right.b=ind.b;

} else right=null;

} else{

res.put(c+1, (long) (i+1) );

if(c>=ind.a) {

left.a = ind.a;

left.b = c; 

} else left=null;

if(c+2<=ind.b) {

right.a = c+2;

right.b=ind.b;

} else right=null;

}

} else{

// odd

c=(ind.a+ind.b)/2;

res.put(c, (long) (i+1));

if(c-1>=ind.a) {

left.a = ind.a;

left.b = c-1; 

} else left=null;

if(c+1<=ind.b) {

right.a = c+1;

right.b=ind.b;

} else right=null;

}

if(left!=null) {

arr.add(left);

insertSort(arr);

}

if(right!=null) {

arr.add(right);

insertSort(arr);

}

// System.out.println(left+" "+right);

// System.out.println("result "+ (c+1)+" "+(i+1));

i++;

}

while(q-->0) {

long a;

a=sc.nextLong();

if(res.containsKey(a)) {

System.out.println(res.get(a));

} else System.out.println(-1);

}

}

}