Problem $1.$ You are given an unsorted array A$[1..$n$]$ of positive integers $($not necessar$-$

ily distinct$).$ We say that an array is satisfiable if$,$ after sorting the array, A$[$i$]>=$ i for all

$1<=$ i $<=$ n$.$

$($a$)$ Design an O$($n$)$ algorithm which determines whether or not A is satisfiable.

$(12\mathrm{.}5$ points$)$

$($b$)$ Design an O$($n$)$ algorithm which takes as input a satisfiable array A and deter$-$

mines the smallest integer that can be appended to A so that the resulting array

remains satisfiable.