package org.example;
import java.util.ArrayList;

public class Program {
     public static void main(String[] args)
     {
          ArrayList<String> myList1 = new ArrayList<String>();

          // добавляем элемент в конец
          myList1.add("Car");
          // myList1 = ["Car"]

          // добавляем элемент в конец
          myList1.add("House");
          // myList1 = ["Car", "House"]

          // добавляем элемент в конец
          myList1.add("Notebook");
          // myList1 = ["Car", "House", "Notebook"]

          // посмотреть элемент по индексу
          String elem = myList1.get(1);
          // elem = "House"
          // myList1 = ["Car", "House", "Notebook"]

          // вставить элемент по индексу 1
          myList1.add(1, "Airplane");
          // myList1 = ["Car", "Airplane", "House", "Notebook"]

          // удалить элемент по индексу
          myList1.remove(1);
          // myList1 = ["Car", "House", "Notebook"]
     }
}

import java.util.ArrayList;

fun main() {

     val myList1 = ArrayList<String>()

     // добавляем элемент в конец
     myList1.add("Car")
     // myList1 = ["Car"]

     // добавляем элемент в конец
     myList1.add("House")
     // myList1 = ["Car", "House"]

     // добавляем элемент в конец
     myList1.add("Notebook")
     // myList1 = ["Car", "House", "Notebook"]

     // посмотреть элемент по индексу
     val elem = myList1[1]
     // elem = "House"
     // myList1 = ["Car", "House", "Notebook"]

     // вставить элемент по индексу 1
     myList1.add(1, "Airplane")
     // myList1 = ["Car", "Airplane", "House", "Notebook"]

     // удалить элемент по индексу
     myList1.removeAt(1)
     // myList1 = ["Car", "House", "Notebook"]
}

class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
     private static final int DEFAULT_CAPACITY = 10;

     transient Object[] elementData; // non-private to simplify nested class access

     private int size;

     public ArrayList(int initialCapacity) {
          if (initialCapacity > 0) {
               this.elementData = new Object[initialCapacity];
          } else if (initialCapacity == 0) {
               this.elementData = EMPTY_ELEMENTDATA;
          } else {
               throw new IllegalArgumentException("Illegal Capacity: "+
                         initialCapacity);
          }
     }

     public ArrayList() {
          this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
     }

     public ArrayList(Collection<? extends E> c) {
          Object[] a = c.toArray();
          if ((size = a.length) != 0) {
               if (c.getClass() == ArrayList.class) {
                    elementData = a;
               } else {
                    elementData = Arrays.copyOf(a, size, Object[].class);
               }
          } else {
               // replace with empty array.
               elementData = EMPTY_ELEMENTDATA;
          }
     }

     public void trimToSize() {
          modCount++;
          if (size < elementData.length) {
               elementData = (size == 0)
                         ? EMPTY_ELEMENTDATA
                         : Arrays.copyOf(elementData, size);
          }
     }

     public void ensureCapacity(int minCapacity) {
          if (minCapacity > elementData.length
                    && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                    && minCapacity <= DEFAULT_CAPACITY)) {
               modCount++;
               grow(minCapacity);
          }
     }

     private Object[] grow(int minCapacity) {
          int oldCapacity = elementData.length;
          if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
               int newCapacity = ArraysSupport.newLength(oldCapacity,
                         minCapacity - oldCapacity, /* minimum growth */
                         oldCapacity >> 1 /* preferred growth */);
               return elementData = Arrays.copyOf(elementData, newCapacity);
          } else {
               return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
          }
     }

     private Object[] grow() {
          return grow(size + 1);
     }

     public int size() {
          return size;
     }

     public boolean isEmpty() {
          return size == 0;
     }

     public boolean contains(Object o) {
          return indexOf(o) >= 0;
     }

     public int indexOf(Object o) {
          return indexOfRange(o, 0, size);
     }

     int indexOfRange(Object o, int start, int end) {
          Object[] es = elementData;
          if (o == null) {
               for (int i = start; i < end; i++) {
                    if (es[i] == null) {
                         return i;
                    }
               }
          } else {
               for (int i = start; i < end; i++) {
                    if (o.equals(es[i])) {
                         return i;
                    }
               }
          }
          return -1;
     }

     public int lastIndexOf(Object o) {
          return lastIndexOfRange(o, 0, size);
     }

     int lastIndexOfRange(Object o, int start, int end) {
          Object[] es = elementData;
          if (o == null) {
               for (int i = end - 1; i >= start; i--) {
                    if (es[i] == null) {
                         return i;
                    }
               }
          } else {
               for (int i = end - 1; i >= start; i--) {
                    if (o.equals(es[i])) {
                         return i;
                    }
               }
          }
          return -1;
     }

     public Object clone() {
          try {
               ArrayList<?> v = (ArrayList<?>) super.clone();
               v.elementData = Arrays.copyOf(elementData, size);
               v.modCount = 0;
               return v;
          } catch (CloneNotSupportedException e) {
               // this shouldn't happen, since we are Cloneable
               throw new InternalError(e);
          }
     }

     public Object[] toArray() {
          return Arrays.copyOf(elementData, size);
     }

     @SuppressWarnings("unchecked")
     public <T> T[] toArray(T[] a) {
          if (a.length < size)
               // Make a new array of a's runtime type, but my contents:
               return (T[]) Arrays.copyOf(elementData, size, a.getClass());
          System.arraycopy(elementData, 0, a, 0, size);
          if (a.length > size)
               a[size] = null;
          return a;
     }

     // Positional Access Operations

     @SuppressWarnings("unchecked")
     E elementData(int index) {
          return (E) elementData[index];
     }

     public E get(int index) {
          Objects.checkIndex(index, size);
          return elementData(index);
     }

     public E getFirst() {
          if (size == 0) {
               throw new NoSuchElementException();
          } else {
               return elementData(0);
          }
     }

     public E getLast() {
          int last = size - 1;
          if (last < 0) {
               throw new NoSuchElementException();
          } else {
               return elementData(last);
          }
     }

     public E set(int index, E element) {
          Objects.checkIndex(index, size);
          E oldValue = elementData(index);
          elementData[index] = element;
          return oldValue;
     }

     private void add(E e, Object[] elementData, int s) {
          if (s == elementData.length)
               elementData = grow();
          elementData[s] = e;
          size = s + 1;
     }

     public boolean add(E e) {
          modCount++;
          add(e, elementData, size);
          return true;
     }

     public void add(int index, E element) {
          rangeCheckForAdd(index);
          modCount++;
          final int s;
          Object[] elementData;
          if ((s = size) == (elementData = this.elementData).length)
               elementData = grow();
          System.arraycopy(elementData, index,
                    elementData, index + 1,
                    s - index);
          elementData[index] = element;
          size = s + 1;
     }

     public void addFirst(E element) {
          add(0, element);
     }

     public void addLast(E element) {
          add(element);
     }

     public E remove(int index) {
          Objects.checkIndex(index, size);
          final Object[] es = elementData;

          @SuppressWarnings("unchecked") E oldValue = (E) es[index];
          fastRemove(es, index);

          return oldValue;
     }

     public E removeFirst() {
          if (size == 0) {
               throw new NoSuchElementException();
          } else {
               Object[] es = elementData;
               @SuppressWarnings("unchecked") E oldValue = (E) es[0];
               fastRemove(es, 0);
               return oldValue;
          }
     }

     public E removeLast() {
          int last = size - 1;
          if (last < 0) {
               throw new NoSuchElementException();
          } else {
               Object[] es = elementData;
               @SuppressWarnings("unchecked") E oldValue = (E) es[last];
               fastRemove(es, last);
               return oldValue;
          }
     }

     public boolean equals(Object o) {
          if (o == this) {
               return true;
          }

          if (!(o instanceof List)) {
               return false;
          }

          final int expectedModCount = modCount;
          // ArrayList can be subclassed and given arbitrary behavior, but we can
          // still deal with the common case where o is ArrayList precisely
          boolean equal = (o.getClass() == ArrayList.class)
                    ? equalsArrayList((ArrayList<?>) o)
                    : equalsRange((List<?>) o, 0, size);

          checkForComodification(expectedModCount);
          return equal;
     }

     boolean equalsRange(List<?> other, int from, int to) {
          final Object[] es = elementData;
          if (to > es.length) {
               throw new ConcurrentModificationException();
          }
          var oit = other.iterator();
          for (; from < to; from++) {
               if (!oit.hasNext() || !Objects.equals(es[from], oit.next())) {
                    return false;
               }
          }
          return !oit.hasNext();
     }

     private boolean equalsArrayList(ArrayList<?> other) {
          final int otherModCount = other.modCount;
          final int s = size;
          boolean equal;
          if (equal = (s == other.size)) {
               final Object[] otherEs = other.elementData;
               final Object[] es = elementData;
               if (s > es.length || s > otherEs.length) {
                    throw new ConcurrentModificationException();
               }
               for (int i = 0; i < s; i++) {
                    if (!Objects.equals(es[i], otherEs[i])) {
                         equal = false;
                         break;
                    }
               }
          }
          other.checkForComodification(otherModCount);
          return equal;
     }

     private void checkForComodification(final int expectedModCount) {
          if (modCount != expectedModCount) {
               throw new ConcurrentModificationException();
          }
     }

     public int hashCode() {
          int expectedModCount = modCount;
          int hash = hashCodeRange(0, size);
          checkForComodification(expectedModCount);
          return hash;
     }

     int hashCodeRange(int from, int to) {
          final Object[] es = elementData;
          if (to > es.length) {
               throw new ConcurrentModificationException();
          }
          int hashCode = 1;
          for (int i = from; i < to; i++) {
               Object e = es[i];
               hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
          }
          return hashCode;
     }

     public boolean remove(Object o) {
          final Object[] es = elementData;
          final int size = this.size;
          int i = 0;
          found: {
               if (o == null) {
                    for (; i < size; i++)
                         if (es[i] == null)
                              break found;
               } else {
                    for (; i < size; i++)
                         if (o.equals(es[i]))
                              break found;
               }
               return false;
          }
          fastRemove(es, i);
          return true;
     }

     private void fastRemove(Object[] es, int i) {
          modCount++;
          final int newSize;
          if ((newSize = size - 1) > i)
               System.arraycopy(es, i + 1, es, i, newSize - i);
          es[size = newSize] = null;
     }

     public void clear() {
          modCount++;
          final Object[] es = elementData;
          for (int to = size, i = size = 0; i < to; i++)
               es[i] = null;
     }

     public boolean addAll(Collection<? extends E> c) {
          Object[] a = c.toArray();
          modCount++;
          int numNew = a.length;
          if (numNew == 0)
               return false;
          Object[] elementData;
          final int s;
          if (numNew > (elementData = this.elementData).length - (s = size))
               elementData = grow(s + numNew);
          System.arraycopy(a, 0, elementData, s, numNew);
          size = s + numNew;
          return true;
     }

     public boolean addAll(int index, Collection<? extends E> c) {
          rangeCheckForAdd(index);

          Object[] a = c.toArray();
          modCount++;
          int numNew = a.length;
          if (numNew == 0)
               return false;
          Object[] elementData;
          final int s;
          if (numNew > (elementData = this.elementData).length - (s = size))
               elementData = grow(s + numNew);

          int numMoved = s - index;
          if (numMoved > 0)
               System.arraycopy(elementData, index,
                         elementData, index + numNew,
                         numMoved);
          System.arraycopy(a, 0, elementData, index, numNew);
          size = s + numNew;
          return true;
     }

     protected void removeRange(int fromIndex, int toIndex) {
          if (fromIndex > toIndex) {
               throw new IndexOutOfBoundsException(
                         outOfBoundsMsg(fromIndex, toIndex));
          }
          modCount++;
          shiftTailOverGap(elementData, fromIndex, toIndex);
     }

     private void shiftTailOverGap(Object[] es, int lo, int hi) {
          System.arraycopy(es, hi, es, lo, size - hi);
          for (int to = size, i = (size -= hi - lo); i < to; i++)
               es[i] = null;
     }

     private void rangeCheckForAdd(int index) {
          if (index > size || index < 0)
               throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
     }

     private String outOfBoundsMsg(int index) {
          return "Index: "+index+", Size: "+size;
     }

     private static String outOfBoundsMsg(int fromIndex, int toIndex) {
          return "From Index: " + fromIndex + " > To Index: " + toIndex;
     }

     public boolean removeAll(Collection<?> c) {
          return batchRemove(c, false, 0, size);
     }

     public boolean retainAll(Collection<?> c) {
          return batchRemove(c, true, 0, size);
     }

     boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end) {
          Objects.requireNonNull(c);
          final Object[] es = elementData;
          int r;
          // Optimize for initial run of survivors
          for (r = from;; r++) {
               if (r == end)
                    return false;
               if (c.contains(es[r]) != complement)
                    break;
          }
          int w = r++;
          try {
               for (Object e; r < end; r++)
                    if (c.contains(e = es[r]) == complement)
                         es[w++] = e;
          } catch (Throwable ex) {
               // Preserve behavioral compatibility with AbstractCollection,
               // even if c.contains() throws.
               System.arraycopy(es, r, es, w, end - r);
               w += end - r;
               throw ex;
          } finally {
               modCount += end - w;
               shiftTailOverGap(es, w, end);
          }
          return true;
     }

     @java.io.Serial
     private void writeObject(java.io.ObjectOutputStream s)
               throws java.io.IOException {
          // Write out element count, and any hidden stuff
          int expectedModCount = modCount;
          s.defaultWriteObject();

          // Write out size as capacity for behavioral compatibility with clone()
          s.writeInt(size);

          // Write out all elements in the proper order.
          for (int i=0; i<size; i++) {
               s.writeObject(elementData[i]);
          }

          if (modCount != expectedModCount) {
               throw new ConcurrentModificationException();
          }
     }

     @java.io.Serial
     private void readObject(java.io.ObjectInputStream s)
               throws java.io.IOException, ClassNotFoundException {

          // Read in size, and any hidden stuff
          s.defaultReadObject();

          // Read in capacity
          s.readInt(); // ignored

          if (size > 0) {
               // like clone(), allocate array based upon size not capacity
               SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
               Object[] elements = new Object[size];

               // Read in all elements in the proper order.
               for (int i = 0; i < size; i++) {
                    elements[i] = s.readObject();
               }

               elementData = elements;
          } else if (size == 0) {
               elementData = EMPTY_ELEMENTDATA;
          } else {
               throw new java.io.InvalidObjectException("Invalid size: " + size);
          }
     }

     public ListIterator<E> listIterator(int index) {
          rangeCheckForAdd(index);
          return new ListItr(index);
     }

     public ListIterator<E> listIterator() {
          return new ListItr(0);
     }

     public Iterator<E> iterator() {
          return new Itr();
     }

     public List<E> subList(int fromIndex, int toIndex) {
          subListRangeCheck(fromIndex, toIndex, size);
          return new SubList<>(this, fromIndex, toIndex);
     }

     @Override
     public void forEach(Consumer<? super E> action) {
          Objects.requireNonNull(action);
          final int expectedModCount = modCount;
          final Object[] es = elementData;
          final int size = this.size;
          for (int i = 0; modCount == expectedModCount && i < size; i++)
               action.accept(elementAt(es, i));
          if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
     }

     @Override
     public Spliterator<E> spliterator() {
          return new ArrayListSpliterator(0, -1, 0);
     }

     @Override
     public boolean removeIf(Predicate<? super E> filter) {
          return removeIf(filter, 0, size);
     }

     boolean removeIf(Predicate<? super E> filter, int i, final int end) {
          Objects.requireNonNull(filter);
          int expectedModCount = modCount;
          final Object[] es = elementData;
          // Optimize for initial run of survivors
          for (; i < end && !filter.test(elementAt(es, i)); i++)
               ;
          // Tolerate predicates that reentrantly access the collection for
          // read (but writers still get CME), so traverse once to find
          // elements to delete, a second pass to physically expunge.
          if (i < end) {
               final int beg = i;
               final long[] deathRow = nBits(end - beg);
               deathRow[0] = 1L; // set bit 0
               for (i = beg + 1; i < end; i++)
                    if (filter.test(elementAt(es, i)))
                         setBit(deathRow, i - beg);
               if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
               modCount++;
               int w = beg;
               for (i = beg; i < end; i++)
                    if (isClear(deathRow, i - beg))
                         es[w++] = es[i];
               shiftTailOverGap(es, w, end);
               return true;
          } else {
               if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
               return false;
          }
     }

     @Override
     public void replaceAll(UnaryOperator<E> operator) {
          replaceAllRange(operator, 0, size);
          // TODO(8203662): remove increment of modCount from ...
          modCount++;
     }

     private void replaceAllRange(UnaryOperator<E> operator, int i, int end) {
          Objects.requireNonNull(operator);
          final int expectedModCount = modCount;
          final Object[] es = elementData;
          for (; modCount == expectedModCount && i < end; i++)
               es[i] = operator.apply(elementAt(es, i));
          if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
     }

     @Override
     @SuppressWarnings("unchecked")
     public void sort(Comparator<? super E> c) {
          final int expectedModCount = modCount;
          Arrays.sort((E[]) elementData, 0, size, c);
          if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
          modCount++;
     }
}