Given an array A$[1...$ n$]$ of n real numbers, give a divide$-$and$-$conquer style algorithm to

compute the number of distinct pairs, which are ordered pairs of indices $($i$,$ j$)$ such that i $<$ j and

A$[$i$]6=$ A$[$j$],$ in O$($n $$ log n$)$ time.

Example:

A $=[1,19,5,19]$

distinct pairs:$(1,2),(1,3),(1,4),(2,3),(3,4).$

count $($your answer$)$ : $5$

$1.$ Describe your algorithm in either English or pseudo$-$code.

$2.$ Argue that your algorithm is correct. Simply restating the steps of the algorithm will receive no credit.

$3.$ Analyze the asymptotic running time of your algorithm.