#include <bits/stdc++.h>
using namespace std;


template<class T>
class Array{
public:
Array(int sizeOfArray=1){
    arr = new T[sizeOfArray];
    for(int i=0;i<sizeOfArray;i++){
        arr[i] = 0;
    }
    maxSize = sizeOfArray;
    currentElement = 0;
}

T* growArray(){
    T* newarr = new T[maxSize*2];
    maxSize = maxSize*2;
    for(int i=0;i<maxSize;i++){
        if(i<maxSize/2){
            newarr[i] = arr[i];
        }
        else{
            newarr[i] = 0;
        }
        }
    delete arr;
    return newarr;
}

T* delete_last_helper(){
    T *newarr = new T[maxSize-1];
    for(int i=0;i<currentElement;i++){
        newarr[i] = arr[i];
    }
    currentElement--;
    maxSize--;
    delete arr;
    return newarr;
}

void deleting_last(){
    arr = delete_last_helper();
}

void add(T element){
    if(currentElement>=maxSize){
        while(currentElement>=maxSize){
            arr = growArray();
        }
    }
    arr[currentElement] = element;
    currentElement++;
}

T* insert_helper(T element, int index){
    if(index>=maxSize){
        while(index>=maxSize){
           arr = growArray();
        }
    }
    T* newarr = new T[maxSize+1];
    maxSize++;
    for(int i=0;i<maxSize;i++){
        if(i<index){
            newarr[i] = arr[i];
        }else if(i==index){
            newarr[i] = element;
        }else if(i>index){
            newarr[i] =  arr[i-1];
        }
    }
    if(index>currentElement){
        currentElement = index;
    }
    else{
        currentElement++;
    }
    delete arr;
    return newarr;
}

void insert_at(T element, int index){
    arr = insert_helper(element, index);
}

T get(int index){
    return arr[index];
}

int nrElements(){
    return currentElement;
}

int length(){
    return maxSize;
}

void delete_array(){
    delete arr;
}

 protected:

 private:
 T* arr;
 int maxSize;
 int currentElement;
 };

 template<class T>
 Array<T> add(Array<T> &arr1, Array<T> &arr2){
 int newsize = arr1.nrElements()+arr2.nrElements()+5;
 int aux;
 Array<T> arr3(newsize);
 for(int i=0;i<arr1.nrElements();i++){
    aux = arr1.get(i);
    arr3.add(aux);
 }
 for(int i=0;i<arr2.nrElements();i++){
    aux = arr2.get(i);
    arr3.add(aux);
 }
  arr1.delete_array();
  arr2.delete_array();
  return arr3;
  }



  int main()
 {

  }