#include <iostream>
#define Nmax 1000

using namespace std;

struct Lista
{
    int t[Nmax];
    int pr, ul;

    /// Initializare lista vida
    void Init()
    {
        pr = 0; ul = -1;
    }

    /// Test lista vida
    int Empty()
    {
        return pr > ul;
    }

    /// Inserare element la sfarsit
    void InsertEnd(int x)
    {
        t[++ul] = x;
    }

    /// Inserare la inceput sau in interior
    void Insert(int poz, int x)
    {
        for(int i = ul; i >= poz + pr - 1; i--)
            t[i+1] = t[i];
        t[poz + pr - 1] = x;
        ul++;
    }

    /// Parcurgerea listei
    void Parcurgere()
    {
        if(Empty()) cout << "Lista este vida!";
        else
        {
            for(int i = pr; i <= ul; i++)
                cout << t[i] << " ";
            cout << "\n";
        }
    }

    /// Stergere de la sfarsit
    void DeleteEnd()
    {
        if(!Empty()) ul--;
    }

    /// Stergere de la inceput
    void DeleteBegin()
    {
        if(!Empty()) pr++;
    }

    /// Sterge elementul de la pozitia poz
    void Delete(int poz)
    {
        if(Empty()) return;
        for(int i = poz + pr - 1; i < ul; i++)
            t[i] = t[i+1];
        ul--;
    }

    /// Accesarea celui de-al k-lea element
    int GetElement(int k)
    {
        return t[pr + k - 1];
    }

    /// Cauta o valoare x in lista
    int Search(int x)
    {
        int i;
        for(i = pr; i <= ul; i++)
            if(t[i] == x) return i - pr + 1;
        return -1;
    }

};

int main()
{
    Lista L;
    L.Init();

    for(int i = 1; i <= 30; i++)
        L.InsertEnd(i*i);
    L.Parcurgere();

    L.Insert(3, 1000);
    L.Parcurgere();

    L.Delete(3);
    L.Parcurgere();

    L.DeleteBegin();
    L.DeleteBegin();
    L.DeleteBegin();
    L.DeleteBegin();
    L.Parcurgere();

    L.DeleteEnd();
    L.Parcurgere();

    cout << "\n" << L.GetElement(4) << "\n";

    cout << L.Search(64) << "\n";

    return 0;
}