Design a fixed-capacity deque with O(1) operations (including search)

Problem You are given a fixed-capacity array of size N. Build a data structure on top of it and implement the following APIs: pushHead(x): insert x to the front popHead(): remove and return the front element pushTail(x): insert x to the back popTail(): remove and return the back element search(x): search for element x in the current structure Requirement: all operations above must run in O(1) time. Assumptions (typical interview defaults) N is given at initialization; the underlying storage cannot grow. popHead/popTail on empty: return -1. pushHead/pushTail on full: return false, otherwise true. search(x) returns whether x exists (true/false). Values are 32-bit integers and may repeat. I/O format (for testing) Read from stdin: Line 1: integers N and Q Next Q lines: one operation per line: pushHead x pushTail x popHead popTail search x Output: For pushHead/pushTail: print true or false For popHead/popTail: print the popped integer (-1 if empty) For search: print true or false Constraints 1 <= N <= 200000 1 <= Q <= 200000 Target overall complexity ~ O(Q) with O(1) per operation. Example Input 3 10 popHead pushHead 1 pushTail 2 pushHead 3 pushTail 4 search 2 search 4 popTail popHead popHead Output -1 true true true false true false 2 3 1