It’s quite simple…

My solution with O(N) preprocessing + O(logN) query

You just need a single observation to boil down this problem into a simple classical problem…

(if the array doesn’t change during the queries)

Here it goes…

Say, the given array is {5,4,3,8,9}

So, By trying various values of M, you can see, the output will never be 4 or 3, because a greater element (5) is already present to the left of both of these elements…

So, it doesn’t matter if you even store these elements.

You simply store the array {5, 8, 9}

Now i believe the binary search will get your answer…

However, if you need index of values rather than the actual values, you may go for mapping these values to their original indices…

If you still need help, refer to following code **only after giving it an attempt**

Hope that helps…

import java.util.*;

class Main{

```
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int N = in.nextInt();
ArrayList<Long> s = new ArrayList<>();
long c = in.nextLong();
s.add(c);
```

for(int i = 1; i < N; i++){

long x = in.nextLong();

if(x <= c)continue;

s.add(x);

c = x;

}

```
int Q = in.nextInt();
while(Q-->0){
long M = in.nextLong();
if(s.get(0) >= M)System.out.println(s.get(0));
else if(s.get(s.size()-1) < M)System.out.println(-1);
else System.out.println(search(s, M, 0, s.size()-1));
}
}
static long search(ArrayList<Long> s, long M, int l, int r){
int mid = (l+r)/2;
if(s.get(mid) >= M && (mid == 0 || s.get(mid-1) < M))return s.get(mid);
else if(s.get(mid) < M)return search(s, M, mid+1, r);
else return search(s,M, l,mid-1);
}
```

}