You can use a deque, but that doesn’t seem to be the correct approach.

In your code, Both find and insertion at the beginning is O(n).

You can use imaginary 2 pointers to solve this.

We first need a map, that lets us know the index of any id in O(1) time.

`vector<int> map(MAXID+1);`

Should suffice.

Now imagine two pointers one at lidx=0, and the other at ridx=1. It’s **NOT** pointing to any real array. We have our imaginary array that supports both `push_back()`

and `push_front()`

in O(1) time. Let’s call that arr[]

Any index i, that satisfies lidx<i<ridx is a valid index.

When we get a query to push book with ID x to the left, We push it to the front, so arr[lidx]=x. We update our map with `map[x]=lidx`

, and then decrease lidx.

When we get a query to push book with ID x to the right, We push it back, so arr[ridx]=x. We update our map with `map[x]=ridx`

, and then increase ridx.

When we get a query to find distance of ID x, we know ridx, so distance from the right is ridx-map[x]-1, The distance from the left is map[x]-lidx-1.

Over here, you notice, That we don’t really need the array itself, so we can consider it to be imaginary.

My submission : Submission #77311965 - Codeforces