write the code for the given question in c$++,$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.

$1)$ 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$).$

$2)$ Megumi Fusigoro: He will choose a $$k$$ 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 $(1<=$ K $<=$ Total tasks$).$

$3)$ Nobara Kugisaki: He will always choose the median ID$.$ If there are $$n$$ tasks in

the list, the median will be defined as $($n $+1)/2($take floor value$)$th ID when all of

them are arranged in ascending order. $($For both odd and even $$n$)$

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 the input, setting list can take O$($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 $=(3+1)/2=2,$ So the $2$nd smallest element is $12.)$