class ArrayList<T> {
	ArrayList(int capacity) {
		this.capacity = capacity;
		arr = (T [])new Object[capacity];
	}
	ArrayList() {this(100);}

	void add(T val) {
		checkSize();
		arr[size++] = val;
	}
	T get(int index) {return arr[index];}
	void set(int index, T val) {arr[index] = val;}
	int size() {return size;}
	void checkSize() {
		if (size < capacity) return;
		capacity *= 2;
		T [] newArr = (T [])new Object[capacity];
		for (int i = 0; i < size; i++)
			newArr[i] = arr[i];
		arr = newArr;
	}

	T [] arr;
	int size = 0, capacity;
}