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 n 2 comparisons/equality test

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 n 2 comparisons in the worst case (i.e., there are inputs where it uses that many comparisons before terminating). Specifically, give an example of a worst- case input for n = 8.