$(2$ points$)($a$)(2$ marks$)$ Shinigami took Light Yagami's special notebook and issued

a challenge. To get it back, Light needs to solve the "Min Max" problem. Light's

task: Given an array of $\text{'}N\text{'}$ integers, determine the maximum values obtained by

taking the minimum element over all possible subarrays of varying sizes from $1$ to

$\text{'}N\text{'}.$

$($b$)($Bonus $3$ marks$)$ Help Light Yagami to solve this problem in $O(n)$ time.

Consider an array, Arr$=[3,1,2,4].$

For subarrays of size $1$: max$(min(3),$min$(1),$min$(2),$min$(4))=4$

For subarrays of size $2$:max$(min(3,1),$min$(1,2),$min$(2,4))=2$

For subarrays of size $3$:max$(min(3,1,2),$min$(1,2,4))=1$

For subarrays of size $4$:max$(min(3,1,2,4))=1$

The resulting array is $4,2,1,1.$