(10%) We are given a sequence $K = \langle k_1, k_2, ..., k_n \rangle$ of $n$ distinct keys in sorted order (so that $k_1 < k_2 < \cdots < k_n$), and we wish to build a binary search tree from these keys. For each key $k_i$, we have a probability $p_i$ that a search will be for $k_i$. Some searches may be for values not in $K$, and so we also have $n+1$ "dummy keys" $d_0, d_1, \ldots, d_n$ representing values not in $K$. In particular, $d_0$ represents all values less than $k_1$, $d_n$ represents all values greater than $k_n$, and for $i = 1, 2, \ldots, n-1$, the dummy key $d_i$ represents all values between $k_i$ and $k_{i+1}$. For each dummy key $d_i$, we have a probability $q_i$ that a search will correspond to $d_i$. Determine the cost and structure of an optimal binary search tree in the expected cost of search time for a set of $n = 7$ keys with the following probabilities: