Below is the code for a MaxPQ $($max ordered priority queue$)$ that is implemented using a sorted linked list. $($The items in the linked list appear in sorted order from greatest to least.$)$ However, the insert method has not been implemented. In the space below the code, write the code for the insert method so that it maintains the invariant that the items in the list appear in sorted order from greatest to least. Note, that the key field in each node implements Comparable, so it will have a compareTo method.

If you cannot answer the question for a generic Key that implements Comparable, you may answer the question assuming the keys are ints and can be compared using $>$ and $<$ for partial credit $($at most $15$ out of $20$ points$)$

public class OrderedMaxPQ$>\{$

private class Node $\{$

Key key;

Node next;

public Node$($Key k$,$ Node n$)\{$

key $=$ k;

next $=$ n;

$\}$

$\}$

private Node first; $//$ The first node in a list where the keys appear in decreasing order

public OrderedMaxPQ$()\{$

first $=$ null;

$\}$

public boolean isEmpty$()\{$

return first $==$ null;

$\}$

public Key delMax$()\{$

if $($isEmpty$())$ throw new NoSuchElementException$("$Priority queue underflow"$)$;

Key answer $=$ first.key;

first $=$ first.next;

return answer;

$\}$

public void insert$($Key k$)\{$

$//$ WRITE YOUR CODE HERE

$\}$

$\}$