ou are a savvy investor who is interested in an especially hot asset that is now on the market: a rare Pikachu Pok $$emon trading card. You want to purchase and sell this card just once, and time these events to maximize your rate of return, i$.$e$.,$ the percentage by which the card$$s value increases between purchase and sale.

Your top trading$-$desk researchers have prepared their best estimates of how much the card$$s value will change on each of the following n days. These estimates are given as nonnegative real multiplicative factors, i$.$e$.,$ a $10\%$ gain is represented by $1\mathrm{.}1,$ and a $20\%$ loss is represented by $0\mathrm{.}8.$ Given the array A$[1,...,$n$]$ of these estimates, you want to find indices $1<=$ i $<=$ j $<=$ n that maximize

A$[$i$]$ A$[$i $+1]$ A$[$j$],$

i$.$e$.,$ the aggregate growth in value if the card is purchased at the start of day i and sold at the

end of day j$.($If the card would lose value every day, this can be indicated by taking i $>$ j$.)$

For instance, if A$[1,...,6]=[0\mathrm{.}8,1\mathrm{.}1,0\mathrm{.}95,1\mathrm{.}5,0\mathrm{.}8,1\mathrm{.}25],$ then the maximum aggregate growth is$1\mathrm{.}5675,$whichisachievedbyi$=2,$j$=6.($Notethatitisalsoachievedbyi$=2,$j$=4.$ So$,$ an optimal choice of i and j is not necessarily unique, but the maximum aggregate growth is unique.$)$

In this question you will design a divide$-$and$-$conquer algorithm that solves this problem. You may assume that two real numbers can be multiplied in constant time, and for simplicity, you may assume that n is a power of two $($if you wish$).$

$($a$)$ Suppose that for some index k of interest, you want to optimize the aggregate growth under the constraint that you own the card on day k and sell it strictly after day k $($i$.$e$.,$ you purchase it at the start of some day i $<=$ k and sell it at the end of some day j $>$ k$).$ Give an algorithm that solves this problem in O$($n$)$ time. On input A$[1,...,$ n$]$ and k$,$ it should output the maximum aggregate growth, and corresponding purchase and sale days i$,$ j that achieve it$.$