You must complete the implementation of UltraFast by correctly coding all eight operations and

optimizing their efficiency. For UltraFast, the running time for get$($i$)$and max$()$must be O$(1),$and

for push$($x$),$pop$(),$set$($i$,$x$),$doubleTop$(),$swapTop$(),$and ksum$($k$)$running time must not

exceed O$($log n$).$ below is the code for UltraSlow.java : package comp$2402$a$4$;

import java.util.List;

import java.util.ArrayList;

import java.util.Iterator;

public class UltraSlow implements UltraStack $\{$

List ds;

public UltraSlow$()\{$

ds $=$ new ArrayList$()$;

$\}$

public void push$($int x$)\{$

ds$.$add$($x$)$;

$\}$

public Integer pop$()\{$

if$($ds$.$size$()==0)$

return null;

return ds$.$remove$($ds$.$size$()-1)$;

$\}$

public Integer get$($int i$)\{$

if$($i $<0||$ i $>=$ ds$.$size$())$

return null;

return ds$.$get$($i$)$;

$\}$

public Integer set$($int i$,$ int x$)\{$

if$($i $<0||$ i $>=$ ds$.$size$())$

return null;

return ds$.$set$($i$,$ x$)$;

$\}$

public void doubleTop$()\{$

if $($size$()>0)$

ds$.$add$($ds$.$get$($ds$.$size$()-1)*2)$;

$\}$

public void swapTop$()\{$

if $($size$()>1)\{$

Integer temp $=$ ds$.$get$($ds$.$size$()-1)$;

ds$.$set$($ds$.$size$()-1,$ ds$.$get$($ds$.$size$()-2))$;

ds$.$set$($ds$.$size$()-2,$ temp$)$;

$\}$

$\}$

public Integer max$()\{$

Integer m $=$ null;

for $($int x : ds$)\{$

if $($m $==$ null $||$ x $>$ m$)\{$

m $=$ x;

$\}$

$\}$

return m;

$\}$

public long ksum$($int k$)\{$

long sum $=0$;

for$($int i$=0$; i iterator$()\{$

return ds$.$iterator$()$;

$\}$

$\}$