1. (4 pts.) Unsorting a sorted array. In a recent lecture, we considered the problem of unsorting a sorted array. Let A be an array containing n numbers in sorted order. To unsort A is to move the elements of A so that no two consecutive entries are the same. Our goal is to design an algorithm that outputs an unsorted version of A if it is possible to unsort A and returns cannot_be_unsorted otherwise. Additionally, we want the algorithm to run in O(n) time. I sketched an algorithm but with some details missing: an implementation for MaxOccurrence(A) that outputs the maximum number of times some number in A occurs and a way to unsorting A when n is odd. a. (2 pts.) Provide an implementation of MaxOccurrence(A) that runs in O(n) time and explain why it is correct. b. (2 pts.) Next, describe what the algorithm should do when n is odd. Again, implement it in O(n) time and prove correctness like what we did in class. 1. (4 pts.) Unsorting a sorted array. In a recent lecture, we considered the problem of unsorting a sorted array. Let A be an array containing n numbers in sorted order. To unsort A is to move the elements of A so that no two consecutive entries are the same. Our goal is to design an algorithm that outputs an unsorted version of A if it is possible to unsort A and returns cannot_be_unsorted otherwise. Additionally, we want the algorithm to run in O(n) time. I sketched an algorithm but with some details missing: an implementation for MaxOccurrence(A) that outputs the maximum number of times some number in A occurs and a way to unsorting A when n is odd. a. (2 pts.) Provide an implementation of MaxOccurrence(A) that runs in O(n) time and explain why it is correct. b. (2 pts.) Next, describe what the algorithm should do when n is odd. Again, implement it in O(n) time and prove correctness like what we did in class