#include <iostream>
#define Nmax 1000

using namespace std;

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

    void Init()
    {
        pr = 0; ul = -1;
    }

    int Empty()
    {
        return pr > ul;
    }

    void InsertEnd(int x)
    {
        t[++ul] = x;
    }

    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++;
    }

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

    void DeleteEnd()
    {
        if(!Empty()) ul--;
    }

    void DeleteBegin()
    {
        if(!Empty()) pr++;
    }

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

    int GetElement(int k)
    {
        return t[pr + k - 1];
    }

    int Search(int x)
    {
        int i;
        for(i = pr; i <= ul; i++)
            if(t[i] == x) return i - pr + 1;
        return -1;
    }

    int Size()
    {
        return ul - pr + 1;
    }

};

int main()
{
    int a[7] = {1, 3, 5, 6, 8, 9, 11}, n = 7;
    int b[10] = {2, 3, 5, 6, 8, 10, 12, 15, 16, 22}, m = 10;
    int i, j;

    Lista L1, L2, L;
    L1.Init();
    L2.Init();
    L.Init();

    for(i = 0; i < n; i++)
        L1.InsertEnd(a[i]);
    for(i = 0; i < m; i++)
        L2.InsertEnd(b[i]);

    i = j = 1;
    int el1, el2;
    while((i <= n) && (j <= m))
    {
        el1 = L1.GetElement(i);
        el2 = L2.GetElement(j);
        if(el1 <= el2)
        {
            L.InsertEnd(el1);
            i++;
        }
        else
        {
            L.InsertEnd(el2);
            j++;
        }
    }
    while(i <= n)
        L.InsertEnd(L1.GetElement(i++));
    while(j <= m)
        L.InsertEnd(L2.GetElement(j++));

    L1.Parcurgere();
    L2.Parcurgere();
    L.Parcurgere();

    return 0;
}