Question $2.(20$ marks$)$ Let $A[1..n]$ be an array about which the following are true:

$($a$)$ The positions of A contain some number $k$ of distinct elements.

$($b$)$ One of these $k$ elements appears in exactly one position of $A$; we will call this unique position singleton$.$

$($c$)$ Each of the remaining $k-1$ elements appears in exactly two consecutive positions of $A$; we will

call a pair of consecutive positions containing the same element a couple.

We want to design an algorithm that, given the array A that satisfies the above properties, returns the

singleton $($i$.$e$.,$ the position of the unique element$).$

There is a straightforward $(n)$ algorithm that does this. Give an asymptotically faster divide$-$and$-$conquer

algorithm that solves this problem. ${?}^1$ Justify the correctness of your algorithm, and analyze its running

time using the Master Theorem.

Hint: What is $n$ in terms of $k?$ Is $n$ even, odd, or could it be either?