If an element is larger than another element and also precedes it we can ignore it, so you can maintain a list of decreasing elements from right to left (Think about it like a stack, but implementation-wise it will probably be better as a vector / deque because of the next step), then perform a binary search on it (pick the biggest that is smaller than K[i])

You can do coordinate compression on all elements in K, then you make a segment tree on array B, where B[x] = latest occurrence of x in array A. So now finding rightmost element in A that is smaller than K[i] becomes a maximum query on range [0; K[i]-1]. After query, update B[K[i]] = i.

In order to make this O(NlogN) with segment trees, do the following.

1. Make a SegmentTree with size equal to k.size() + a.size().

2. At the start, push all elements from A there, and then, when you have to add k[i], call point update on pos = a.size() + i (so make a[a.startSize + i] = k[i])

3. Then, do the following:

Call recursively from Node V(at the start, this is the node responsible for the whole segment): Consider its two sons

If the right son is v.r and left son is v.l, you can do the following:

if v.r min < k[i], then there exists an element there less than k[i], and you need to only consider that segment (call recursively from v.r) otherwise, call from v.l, as that's where the minimum is

This technique is called descending the Segment Tree

Simple stack dude:)

Next time, can you post where you got the problem statement from? I know it can be a pain, but it ensures that we are not abetting in cheating from some ongoing contest.