/* problem link : https://www.codechef.com/problems/FAKEBS
my submission link : https://www.codechef.com/viewsolution/46251958
Approach :
--> For a particular x, we will find the # of elements < x and > x.
--> Then we do a binary search in arr, if arr[mid] ==x we stops
--> if the x is on left side of mid, we need > x element at mid
--> if x is on right side of mid, we need < x element at mid.
*/
public static void solve() {
int n = sc.nextInt();
int q = sc.nextInt();
int[] arr = new int[n];
for(int i=0;i<n;i++)arr[i] = sc.nextInt();
//this map will store element with their index
Map<Integer,Integer> findIndex = new HashMap<>();
int[] temp = new int[n]; // sorted version of given array
for(int i=0;i<n;i++){
findIndex.put(arr[i],i);
temp[i] = arr[i];
}
sort(temp,true); // sort temp in non decreasing order
StringBuilder sb = new StringBuilder();
for(int i=0;i<q;i++) {
int x = sc.nextInt();
sb.append(bs(findIndex, arr, x,temp)).append("\n");
}
out.print(sb);
}
// this function gives us # of swaps or -1 if not possible
private static int bs(Map<Integer,Integer> findIndex,int[] arr,int x,int[] temp){
int n = arr.length;
int z = bs2(temp,0,n-1,x); // find index of x in temp
int less = z; // # of elements < x
int more = n-1-z;// # of elements > x
int l = 0;
int r = arr.length-1;
int swaps = 0;
while (l<=r){
int mid = (r-l)/2 + l;
if(arr[mid]==x)return swaps; // if element found we return # of swaps
else if(findIndex.get(x)<mid){ // element x is on left side of mid
if(more==0)break; // if we have no >x element break and return -1
more--;
if(arr[mid]<x)swaps++; // if arr[mid] < x , then only we need to swap it with a greater element.
r = mid-1;
}else { // element x is on right side of mid
if(less==0)break; // if we have no < x element break and return -1
less--;
if(arr[mid]>x)swaps++; // if arr[mid] > x , then only we need to swap it with a smaller element.
l = mid+1;
}
}
return -1;
}
// this binary search return the index of element x
private static int bs2(int[] arr,int l,int r,int x){
int mid = (r-l)/2+l;
if(arr[mid]==x)return mid;
if(arr[mid]>x)return bs2(arr,l,mid-1,x);
return bs2(arr,mid+1,r,x);
}