#include <iostream>

using namespace std;


template <typename TElement>
class Sequence {
protected:
    int length;
    bool isEmpty;
public:
    Sequence();
    ~Sequence();
    virtual TElement Get (int index) = 0;
    virtual TElement GetFirst() = 0;
    virtual TElement GetLast () = 0;
    // virtual Sequence<TElement> GetSubsequence (int startIndex, int endIndex) = 0;
    virtual void Append (TElement item) = 0;
    virtual void Prepend (TElement item) = 0;
    virtual void InsertAt (int index, TElement item) = 0;
    virtual void Remove (TElement item) = 0;

};
template <typename TElement>
Sequence<TElement>::Sequence() {
    length = 0;
    isEmpty = true;
}

template <typename TElement>
Sequence<TElement>::~Sequence() {

}


template <typename TElement>
class ArraySequence : public Sequence<TElement> {
private:
    TElement *Array;
public:
    ArraySequence();
    ~ArraySequence();
    TElement Get (int index);
    TElement GetFirst();
    TElement GetLast ();
    ArraySequence<TElement> GetSubsequence (int startIndex, int endIndex);
    void Append (TElement item);
    void Prepend (TElement item);
    void InsertAt (int index, TElement item);
    void Remove (TElement item);

    //
    void qwe(TElement *array);
    void print_all ();
};

template <typename TElement>
ArraySequence<TElement>::ArraySequence() {
    Array = new TElement;
}

template <typename TElement>
ArraySequence<TElement>::~ArraySequence() {
    delete Array;
}

template <typename TElement>
TElement ArraySequence<TElement>:: Get (int index) {
    try {
        if (index < 0 || index >= this->length) {
            throw 999;
        }
        return Array[index];
    }
    catch (int str) {
        cout << str << endl;
        exit(0);
    }

    return Array[index];
}

template <typename TElement>
TElement ArraySequence<TElement>:: GetFirst () {
    return Array[0];
}

template <typename TElement>
TElement ArraySequence<TElement>:: GetLast() {
    return Array [this->length - 1];
}
template <typename TElement>    // удалить потом
void ArraySequence<TElement>:: qwe(TElement *array) {
    Array = array;
}

template <typename TElement>
void ArraySequence<TElement>:: Append(TElement item) {  // Append. вставить в конец
    if (this->length == 0) {
        this->length ++;
        this->isEmpty = false;
        Array [0] = item;
    }
    else {
        this->length ++;
        TElement *newArray = new TElement [this->length];
        for (int i = 0; i < this->length - 1; i++) {
            newArray[i] = Array [i];
        }
        newArray[this->length - 1] = item;
        Array = newArray;
    }
}

template <typename TElement>
void ArraySequence<TElement>:: Prepend(TElement item) {  // Prepend. вставить в начало
    if (this->length == 0) {
        this->length ++;
        this->isEmpty = false;
        Array [0] = item;
    }
    else {
        this->length ++;
        TElement *newArray = new TElement [this->length];
        for (int i = 1; i < this->length; i++) {
            newArray[i] = Array [i-1];
        }
        newArray[0] = item;
        Array = newArray;
    }
}

template <typename TElement>
void ArraySequence<TElement>:: InsertAt(int index, TElement item) {
    if (index == 0) {
        this->Prepend(item);
    }
    if (index == this->length) this->Append(item);  // или вообще запретить это?
    else {
        this->length ++;
        TElement *newArray = new TElement [this->length];
        for (int i = 0; i < index; i ++) {
            newArray[i] = Array[i];
        }
        newArray[index] = item;
        for (int i = index + 1; i < this->length; i++) {
            newArray [i] = Array [i-1];
        }
        Array = newArray;
    }
}


template <typename TElement>
void ArraySequence<TElement>:: Remove(TElement item) {
    for (int i = 0; i < this->length; i ++) {
        //cout << Array[i] << " ";
        if (Array[i] == item) {
            this->length --;
            TElement *newArray = new TElement [this->length];
            for (int j = 0; j < i; j ++) {
                newArray[j] = Array [j];
            }
            for (int k = i; k < this->length; k ++) {
                newArray[k] = Array[k+1];
            }
            Array = newArray;
            i --;
        }
    }
}

template <typename TElement>
ArraySequence<TElement> ArraySequence<TElement>:: GetSubsequence(int startIndex, int endIndex) {
    ArraySequence<TElement> Subsequence;
    for (int i = startIndex; i <= endIndex; i ++) {
        Subsequence.Append(Array[i]);
    }
    return Subsequence;
}


template <typename TElement>
void ArraySequence<TElement>:: print_all() {
    for (int i = 0; i < this->length; i ++) {
        cout << Array[i] << endl;
    }
}