// Copyright (C) 2002-2017 Sebastiano Vigna

public class IntArrayList extends AbstractIntList implements RandomAccess, Cloneable, java.io.Serializable {
	public static final int DEFAULT_INITIAL_CAPACITY = 16;
	protected transient int a[];
	protected int size;
	private static final boolean ASSERTS = false;
	
	protected *(final int a[], @SuppressWarnings("unused") boolean dummy) {
		this.a = a;
	}
	
	*(final int capacity) {
		if (capacity < 0)
			throw new IllegalArgumentException("Initial capacity (" + capacity + ") is negative");
		a = new int[capacity];
	}
	
	*() {
		this(DEFAULT_INITIAL_CAPACITY);
	}
	
	*(final Collection<? extends Integer> c) {
		this(c.size());
		size = IntIterators.unwrap(IntIterators.asIntIterator(c.iterator()), a);
	}
	
	*(final IntCollection c) {
		this(c.size());
		size = IntIterators.unwrap(c.iterator(), a);
	}
	
	*(final IntList l) {
		this(l.size());
		l.getElements(0, a, 0, size = l.size());
	}
	
	*(final int a[]) {
		this(a, 0, a.length);
	}
	
	*(final int a[], final int offset, final int length) {
		this(length);
		System.arraycopy(a, offset, this.a, 0, length);
		size = length;
	}
	
	public int[] elements() {
		return a;
	}
	
	static IntArrayList wrap(final int a[], final int length) {
		if (length > a.length)
			throw new IllegalArgumentException(
					"The specified length (" + length + ") is greater than the array size (" + a.length + ")");
		final IntArrayList l = new IntArrayList(a, false);
		l.size = length;
		return l;
	}
	
	static IntArrayList wrap(final int a[]) {
		return wrap(a, a.length);
	}
	
	public void ensureCapacity(final int capacity) {
		a = IntArrays.ensureCapacity(a, capacity, size);
		if (ASSERTS)
			assert size <= a.length;
	}
	
	private void grow(final int capacity) {
		a = IntArrays.grow(a, capacity, size);
		if (ASSERTS)
			assert size <= a.length;
	}
	@Override
	public void add(final int index, final int k) {
		ensureIndex(index);
		grow(size + 1);
		if (index != size)
			System.arraycopy(a, index, a, index + 1, size - index);
		a[index] = k;
		size++;
		if (ASSERTS)
			assert size <= a.length;
	}
	@Override
	public boolean add(final int k) {
		grow(size + 1);
		a[size++] = k;
		if (ASSERTS)
			assert size <= a.length;
		return true;
	}
	@Override
	public int getInt(final int index) {
		if (index >= size)
			throw new IndexOutOfBoundsException(
					"Index (" + index + ") is greater than or equal to list size (" + size + ")");
		return a[index];
	}
	@Override
	public int indexOf(final int k) {
		for (int i = 0; i < size; i++)
			if (((k) == (a[i])))
				return i;
		return -1;
	}
	@Override
	public int lastIndexOf(final int k) {
		for (int i = size; i-- != 0;)
			if (((k) == (a[i])))
				return i;
		return -1;
	}
	@Override
	public int removeInt(final int index) {
		if (index >= size)
			throw new IndexOutOfBoundsException(
					"Index (" + index + ") is greater than or equal to list size (" + size + ")");
		final int old = a[index];
		size--;
		if (index != size)
			System.arraycopy(a, index + 1, a, index, size - index);
		if (ASSERTS)
			assert size <= a.length;
		return old;
	}
	@Override
	public boolean rem(final int k) {
		int index = indexOf(k);
		if (index == -1)
			return false;
		removeInt(index);
		if (ASSERTS)
			assert size <= a.length;
		return true;
	}
	@Override
	public int set(final int index, final int k) {
		if (index >= size)
			throw new IndexOutOfBoundsException(
					"Index (" + index + ") is greater than or equal to list size (" + size + ")");
		int old = a[index];
		a[index] = k;
		return old;
	}
	@Override
	public void clear() {
		size = 0;
		if (ASSERTS)
			assert size <= a.length;
	}
	@Override
	public int size() {
		return size;
	}
	@Override
	public void size(final int size) {
		if (size > a.length)
			ensureCapacity(size);
		if (size > this.size)
			Arrays.fill(a, this.size, size, (0));
		this.size = size;
	}
	@Override
	public boolean isEmpty() {
		return size == 0;
	}
	/**
	 * Trims this array list so that the capacity is equal to the size.
	 *
	 * @see java.util.ArrayList#trimToSize()
	 */
	public void trim() {
		trim(0);
	}
	
	public void trim(final int n) {
		// TODO: use Arrays.trim() and preserve type only if necessary
		if (n >= a.length || size == a.length)
			return;
		final int t[] = new int[Math.max(n, size)];
		System.arraycopy(a, 0, t, 0, size);
		a = t;
		if (ASSERTS)
			assert size <= a.length;
	}
	
	public void getElements(final int from, final int[] a, final int offset, final int length) {
		IntArrays.ensureOffsetLength(a, offset, length);
		System.arraycopy(this.a, from, a, offset, length);
	}
	
	public void removeElements(final int from, final int to) {
		it.unimi.dsi.fastutil.Arrays.ensureFromTo(size, from, to);
		System.arraycopy(a, to, a, from, size - to);
		size -= (to - from);
	}
	
	public void addElements(final int index, final int a[], final int offset, final int length) {
		ensureIndex(index);
		IntArrays.ensureOffsetLength(a, offset, length);
		grow(size + length);
		System.arraycopy(this.a, index, this.a, index + length, size - index);
		System.arraycopy(a, offset, this.a, index, length);
		size += length;
	}
	
	@Override
	public int[] toArray(int a[]) {
		if (a == null || a.length < size)
			a = new int[size];
		System.arraycopy(this.a, 0, a, 0, size);
		return a;
	}
	@Override
	public boolean addAll(int index, final IntCollection c) {
		ensureIndex(index);
		int n = c.size();
		if (n == 0)
			return false;
		grow(size + n);
		if (index != size)
			System.arraycopy(a, index, a, index + n, size - index);
		final IntIterator i = c.iterator();
		size += n;
		while (n-- != 0)
			a[index++] = i.nextInt();
		if (ASSERTS)
			assert size <= a.length;
		return true;
	}
	
	@Override
	public boolean addAll(final int index, final IntList l) {
		ensureIndex(index);
		final int n = l.size();
		if (n == 0)
			return false;
		grow(size + n);
		if (index != size)
			System.arraycopy(a, index, a, index + n, size - index);
		l.getElements(0, a, index, n);
		size += n;
		if (ASSERTS)
			assert size <= a.length;
		return true;
	}
	
	@Override
	public boolean removeAll(final IntCollection c) {
		final int[] a = this.a;
		int j = 0;
		for (int i = 0; i < size; i++)
			if (!c.contains(a[i]))
				a[j++] = a[i];
		final boolean modified = size != j;
		size = j;
		return modified;
	}
	
	@Override
	public boolean removeAll(final Collection<?> c) {
		final int[] a = this.a;
		int j = 0;
		for (int i = 0; i < size; i++)
			if (!c.contains(Integer.valueOf(a[i])))
				a[j++] = a[i];
		final boolean modified = size != j;
		size = j;
		return modified;
	}
	
	@Override
	public IntListIterator listIterator(final int index) {
		ensureIndex(index);
		return new IntListIterator() {
			int pos = index, last = -1;
			@Override
			public boolean hasNext() {
				return pos < size;
			}
			@Override
			public boolean hasPrevious() {
				return pos > 0;
			}
			@Override
			public int nextInt() {
				if (!hasNext())
					throw new NoSuchElementException();
				return a[last = pos++];
			}
			@Override
			public int previousInt() {
				if (!hasPrevious())
					throw new NoSuchElementException();
				return a[last = --pos];
			}
			@Override
			public int nextIndex() {
				return pos;
			}
			@Override
			public int previousIndex() {
				return pos - 1;
			}
			@Override
			public void add(int k) {
				IntArrayList.this.add(pos++, k);
				last = -1;
			}
			@Override
			public void set(int k) {
				if (last == -1)
					throw new IllegalStateException();
				IntArrayList.this.set(last, k);
			}
			@Override
			public void remove() {
				if (last == -1)
					throw new IllegalStateException();
				IntArrayList.this.removeInt(last);
				/*
				 * If the last operation was a next(), we are removing an element *before* us,
				 * and we must decrease pos correspondingly.
				 */
				if (last < pos)
					pos--;
				last = -1;
			}
		};
	}
	
	@Override
	public IntArrayList clone() {
		IntArrayList c = new IntArrayList(size);
		System.arraycopy(a, 0, c.a, 0, size);
		c.size = size;
		return c;
	}
}

/**
 * A type-specific array-based list; provides some additional methods that use
 * polymorphism to avoid (un)boxing.
 *
 * <p>
 * This class implements a lightweight, fast, open, optimized, reuse-oriented
 * version of array-based lists. Instances of this class represent a list with
 * an array that is enlarged as needed when new entries are created (by doubling
 * its current length), but is <em>never</em> made smaller (even on a
 * {@link #clear()}). A family of {@linkplain #trim() trimming methods} lets you
 * control the size of the backing array; this is particularly useful if you
 * reuse instances of this class. Range checks are equivalent to those of
 * {@link java.util}'s classes, but they are delayed as much as possible. The
 * backing array is exposed by the {@link #elements()} method.
 *
 * <p>
 * This class implements the bulk methods {@code removeElements()},
 * {@code addElements()} and {@code getElements()} using high-performance system
 * calls (e.g., {@link System#arraycopy(Object,int,Object,int,int)
 * System.arraycopy()} instead of expensive loops.
 *
 * @see java.util.ArrayList
 */