$(25$ points$)$ Various organizations rank universities worldwide every year. These

rankings are often controversial and do not always agree with each other. Alice

wants to find out the level of $($in$)$consistency between the QS ranking and the US

News ranking. Consider $n$ universities. For each university $1in,q_i$ and $u_i$

are its ranks accoording to QS and US News respectively. $($Hence$,q_1,q_2,$dots,$q_n$ and

$u_1,u_2,dots{u}_n$ are two permutations of $1$ to $n.)$ We call a pair of universities $i,j$ a

"disagreement" if $q_i>q_j$ and $O(n^2)O(nlogn)u_i.$ Design a divide and conquer algorithm for

finding the number $of$ "disagreements" between the $QS$ and $US$ News rankings. Your

algorithm shall have running time strictly faster than $O(n^2)$; $to$ get full credit, your

algorithm shall have running time $O(nlogn).$