$(20$ points$)$ You are given a positive integer k and an array A$[1..$n$]$ that stores n possibly non$-$distinct integer scores in the range $1,100.$ The scores in A are stored in non$-$decreasing order. The scores are conceptually divided into k groups such that for iin$[1,$k$],$ group i consists of scores in the range $(100($i$-1)/($k$),100($i$)/($k$)].$ Your task is to design an algorithm to count the number of scores in group i and store the count in the array G$[1..$k$].$ The count for group i should be stored in the entry G$[$i$].$ Your algorithm cannot directly access A$[$j$]$ for any jin$[1,$n$]$ or G$[$i$]$ for any iin$[1,$k$].$ Instead, it can only access and$/$or modify A and G using the following three functions: Init$($G$)$ : It initializes all entries of G to zero in O$($k$)$ time. Compare $($r$,$s$)$ : For i$,$jin$[1,$n$],$ it compares A$[$r$]$ and A$[$s$]$ and re$-$ turns true if A$[$r$]$ and A$[$s$]$ belong to the same group, otherwise false. This takes O$(1)$ time. Increase$($j$,$x$)$ : For jin$[1,$n$],$ it finds the index i of the group that contains A$[$j$]$ and adds x to G$[$i$].$ This function takes O$(1)$ time. Your task is to design an algorithm with the following running time re$-$ quirements. Explain its correctness and analyze its running time. $($Note: A correct answer to $(2)$ will get you all $20$ points, so you don't have to do $(1)$ if you are certain about your answer to $(2).)(1)(10$ points$)$ Design an algorithm that runs in O$($klogn$)$ time. $(2)(10$ points$)$ Design an algorithm that runs in O$($klog$(($n$)/($k$)))$ time. Hint: Let x$\_($i$)$ be the size of group i for iin$[1,$k$].$ Subject to x$\_(1)+$x$\_(2)+$ dots$+$x$\_($k$)=$n $,$ the product x$\_(1)*$x$\_(2)$cdotscdotsx$\_($n$)$ is maximized when x$\_($i$)=($n$)/($k$)$ for all iin$[1,$k$].$