$(15$ points$)$ Jujutsu High has $3$ freshmen, Yuji Itadori, Magumi Fusigoro, and Nobara Kugisaki. They are assigned a list of tasks they must finish together. Each task has a unique ID$.$ However, each has a weird way of choosing their task from the remaining tasks in the list.

Yuji Itadori: Always chooses the tasks with the max or min ID$.$ Min or Max is decided randomly by him $($assume $50\%$ probability for each min or max$).$

Megumi Fusigoro: He will choose a $\text{'}$k$\text{'}$ and call the kth smallest ID $($Kth ID when all IDs are arranged in ascending order$).K$ is chosen randomly from the total tasks available in the list Total tasks$).$

Nobara Kugisaki: He will always choose the median ID$.$ If there are $\text{'}n\text{'}$ tasks in the list, the median will be defined as $\frac{n+1}{2}($take floor value$)$th ID when all of them are arranged in ascending order. $($For both odd and even $\text{'}n\text{'})$

Page $3$

Sataru Gojo wants to digitize this process of choosing tasks and is asking for your suggestions on the data structure that would be ideal for this scenario. Your task is to design a data structure that supports the query of each of the three freshmen. The data structure should be highly efficient. It should return the task ID in $O(log(n))$ for all $3$ scenarios.

Note:$-$ Once the task is assigned to someone, it can't be reassigned to someone else. It must be deleted from your data structure. Taking input elements, setting them in your data structure can take $O(n)$ or $O(nlog(n)),$ but query execution should be in $O(log(n)).$

Input example: a list of unique task IDs $=[34,56,12,44,10]$ and query $1,2,$ or $3.$ Return the task ID for the corresponding candidate.

Input Query: $1$

Output: $56($Max element, $56$ is no longer available in the list after query $1)$

Input Query: $2$

Enter k: $3$

Output: $34(3$rd smallest in the list.$)$

Input Query: $3$

Output: $12($Initial length was $n=5$; after removing $2$ elements, the new length is $n=3.$ median $=\frac{3+1}{2}=2,$ So the $2$ nd smallest element is $12.$