/** The lock protecting all mutators */
 final transient ReentrantLock lock = new ReentrantLock();

 /** The array, accessed only via getArray/setArray. */
 private transient volatile Object[] array;

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }

static final class COWIterator<E> implements ListIterator<E> {
    /** Snapshot of the array */
    private final Object[] snapshot;
    /** Index of element to be returned by subsequent call to next.  */
    private int cursor;

    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }

class Solution {
 public int binarySearch(int[] arr,int x){
        int left = 0;
        int right = arr.length -1;
        while(left <= right){
            int index = (right -left)/2+left;
            int value = arr[index];
            
            if(value == x){
                return index;
            }else if(value > x){
                right = index - 1;
            }else if(value < x){
                if(index + 1 < (arr.length -1)){
                    int next = arr[index+1];
                    if(next < x){
                        left = index + 1;
                        continue;
                    }
                    int comp = (next - x) - (x - value);
                    if(comp >= 0){
                        return index;
                    }else{
                        return index+1;
                    }
                }else{
                    return index;
                }
                  
            }
        }
        return -1;
    }
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int flag = binarySearch(arr,x);
        if(flag == -1){
            List<Integer> list = new ArrayList<Integer>();
            for(int i = 0 ; i<k;i++){
                list.add(arr[i]);
            }
            return list;
        }
        int nums = k-1;
        int left = flag;
        int right = flag;
        int size = arr.length;
        while(nums != 0){
            int innerLeft = left;
            int innerRight = right;
            if(right + 1 > size -1){
                left = innerLeft -1;
                nums--;
                continue;
            }else if(left -1 < 0){
                right = innerRight + 1;
                nums--;
                continue;
            }else{
                if( right + 1 <= size - 1 ){
                    innerRight = innerRight + 1;
                }
                if(left -1 >= 0){
                    innerLeft = innerLeft -1;
                }
            }        
            int leftValue = arr[innerLeft];
            int rightValue = arr[innerRight];
            int leftDiv = x - leftValue;
            int rightDiv = rightValue - x;
            if(leftDiv <= rightDiv){
                left = innerLeft;
            }else{
                right = innerRight;
            }           
            nums--;       
        }
        List<Integer> list2 = new ArrayList<Integer>();
        for(int i = left ; i<= right;i++){
            list2.add(arr[i]);
        }
        return list2;
    }
}

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData
/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }

class LRUCache {
    private LinkedHashMap<Integer,Integer> map;
    private int capacity;

    public LRUCache(int capacity) {
        map = new LinkedHashMap<Integer,Integer>(capacity,0.75f,true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        Integer value = map.get(key);
        if(value == null){
            return -1;
        }else{
            return value;
        }
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            map.remove(key);
        }
        if(map.size() >= capacity){
            map.remove(map.keySet().iterator().next());
        }
        map.put(key,value);
    }
}

class LRUCache {
    private int capacity;
    private Map<Integer,Node> map;
    private Node head;
    private Node tail;
    
    class Node{
        int key;
        int value;
        Node pre;
        Node next;
        public Node(int key,int value){
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int capacity) {
        map = new HashMap<Integer,Node>();
        this.capacity = capacity;
        
    }
     public int get(int key) {
        //空表处理
        Node node = map.get(key);
        if(node == null){
            return -1;
        }
        //存在就删除这个结点，放到head上，要判断head和tail为空的情况
        removeNode(node);
        insertHead(node);
        return node.value;
    }
     private void removeNode(Node node){
         //存在就删除这个结点，放到head上，要判断head和tail为空的情况
        Node pre = node.pre;
        Node next = node.next;
      
        if(node == tail && node == head){
            head = tail = null;
        }else if(node == tail){
          
            pre.next = null;
            tail = pre;
            
        }else if(node == head){
          
            next.pre =  null;
            head = next;
            
        }else{
          
            pre.next = next;
            next.pre = pre;
        }
       
        map.remove(node.key);
        
    }
     private void insertHead(Node node){
        //插入头部要判断head的空问题
        if(head == null){
            head = node;
            tail = node;
        }else{
            Node oldHead = head;
            node.next = oldHead;
            oldHead.pre = node;
            head = node;
        }
        map.put(node.key,node);
        
    }
    private void removeTail(){
        
        if(tail == null){
            return;
        }
      
        map.remove(tail.key);
        if(tail.pre == null){
            tail = head = null;
        }else{
            tail = tail.pre;
            tail.next = null;
        }
        
    }
    public void put(int key, int value) {
        Node node = map.get(key);

        if(map.size() < capacity){       
            if(node != null){
                removeNode(node);          
            }
            Node newNode = new Node(key,value);
            insertHead(newNode);
            map.put(key,newNode);
        }else if(map.size() == capacity){
            if(node != null){
                removeNode(node);  
                insertHead(new Node(key,value));
            }else{
                removeTail();  
                Node newNode = new Node(key,value);
                insertHead(newNode);
            }
        }
        //小于容量，看是否存在，存在删除，直接放在head
        //等于容量，看是否存在，存在删除，直接放在head
        //不存在，删除tail，放在head

    }
}

class LRUCache {
    private int capacity;
    private Map<Integer,Node> map;
    //dummy
    private Node head;
    private Node tail;
    
    class Node{
        int key;
        int value;
        Node pre;
        Node next;
        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
        public Node(){
            
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<Integer,Node>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if(node == null){
            return -1;
        }
        removeNode(node);
        insertHeadNode(node);
        return node.value;
    }
     public void put(int key, int value) {
        int size = map.size();
        Node node = map.get(key);
        if(node == null){
            if(size == capacity){
                removeTail();
            }         
        }else{
            
            removeNode(node);
            
        }
        Node newNode = new Node(key,value);
        insertHeadNode(newNode);
    }
    private void removeTail(){
        Node preNode = tail.pre;
      
        if(preNode == head){
            return;
        }
        Node node = preNode.pre;
        node.next = tail;
        tail.pre = node;
        map.remove(preNode.key);
    }
    private void removeNode(Node node){
        Node pre = node.pre;
        Node next = node.next;
        map.remove(node.key);
        
        pre.next = next;
        next.pre = pre;
    }
     private void insertHeadNode(Node node){
        Node oldNext = head.next;
        
        node.next = oldNext;
        head.next = node;
        
        node.pre = head;
        oldNext.pre = node;
        
        map.put(node.key,node);
    }
}