$(20$ points$)$ Let $A[1..n]$ be an array of $n$ possibly non$-$distinct integers.

The array A may not be sorted. The $q-$th quantiles of $A[1..n]$ are the $k-$

th smallest elements of A for $k={|}_{{?}_{?}}\frac{n}{q_{{?}_{?}}}|,{|}_{{?}_{?}}2\frac{n}{q_{{?}_{?}}}|,$dots,${|}_{{?}_{?}}(q-1)\frac{n}{q_{{?}_{?}}}|.$ Note

that the $q-$th quantiles consist of $q-1$ elements of $A.$

For example, if $A=[5,8,16,2,7,11,0,9,3,4,6,7,3,15,5,12,4,7],$ the $3$rd

quantiles of A are $\{4,7\},$ because the $3$ rd quantiles consist of the $6-$th and

$12-$th smallest elements of $A,$ which are $4$ and $7,$ respectively.

Suppose you have a black box worst$-$case linear$-$time algorithm that can

find the median of an array of integers. That is$,$ this algorithm runs in

$O(s)$ time on an array of size $s.$ Describe an algorithm that determines the

$q-$th quantiles of $A[1..n]$ in $O(nlogq)$ time. Argure that your algorithm

is correct. Derive the running time of your algorithm.