1. Modify BinarySearchST (Algorithm 3.2 in textbook on page 379) so that inserting a key that is larger than all keys in the table takes con- stant time (so that building a table by calling put() for keys that are in order takes linear time). [6 marks] ALGORITHM 3.2 Binary search (in an ordered array) public class BinarySearchST, Value> private key[] keys; private Value[] vals; private int N; public BinarySearchST(int capacity) { // See Algorithm i.1 for standard array-resizing code. keys = (Key[]) new Comparable[capacity]; vals - (Value[]) new Object[capacity]: } public int size() { return N; } public Value get(key key) if (isempty()) return null; int i = rank (key); if (i i; j--) { keys [j] = keys [j-1]; vals[j] = vals[j-1]; } keys[i] = key; vals[i] = val; N++; } public void delete(key key) // See Exercise 3.1.16 for this method. } This ST implementation keeps the keys and values in parallel arrays. The put() implementation moves larger keys one position to the right before growing the table as in the array-based stack imple- mentation in SECTION 1.3. Array-resizing code is omitted here