Consider an array A with n elements where it is guaranteed that every element appears exactly twice in A, e.g., A=(9,7,7,1,9,1,3,5,3,5). For any two elements A[i],A[j] in the array, we may only compare the elements by testing equality, i.e., A[i]=?A[j]. With this in mind, 1. Give an algorithm that returns two positions in A that have the same element using at most n2 comparisons/equality tests. Note: These may be any two positions, so for example (1,5),(2,3),(4,6),(7,9) or (8,10) are all valid outputs of this algorithm on A. 2. Prove that your algorithm really needs n2 comparisons in the worst case (i.e., there are inputs where it uses that many comparisons before terminating). Specifically, give an example of a worstcase input for n=8