#include <iostream>
#include <fstream>
#include <set>

class BSequence
{
    int maximum;
    std::set<int> ascendingHalf;
    std::set<int, std::greater<int>> descendingHalf;

public:
    BSequence(std::string fileName)
    {
        std::ifstream fin(fileName);

        int nr1, nr2;
        bool ascending = true;

        fin >> nr1;

        while (fin >> nr2)
        {
            if (nr1 > nr2)
            {
                if (ascending)
                    maximum = nr1, ascending = false;
                else if (ascendingHalf.find(nr1) != ascendingHalf.end())
                    descendingHalf.insert(nr1);
            }
            else
                ascendingHalf.insert(nr1);

            nr1 = nr2;
        }

        if (ascending)
            maximum = nr1;
        else
            descendingHalf.insert(nr1);

        fin.close();
    }

    bool insert(int nr)
    {
        if (nr == maximum)
            return false;

        if (ascendingHalf.find(nr) == ascendingHalf.end())
            ascendingHalf.insert(nr);
        else if (descendingHalf.find(nr) == descendingHalf.end())
            descendingHalf.insert(nr);
        else
            return false;

        return true;
    }

    void print()
    {
        for (int nr : ascendingHalf)
            std::cout << nr << " ";
        std::cout << maximum << " ";
        for (int nr : descendingHalf)
            std::cout << nr << " ";
        std::cout << std::endl;
    }
};

int main()
{
    BSequence bs("input.txt");

    std::cout << "Initial sequence: ";
    bs.print();

    int nrOperations;
    std::cout << "Number of operations: ";
    std::cin >> nrOperations;

    for (int i = 0; i < nrOperations; i++)
    {
        int val;
        std::cout << "Insert value: ";
        std::cin >> val;

        bool wasInserted = bs.insert(val);

        if (wasInserted)
            std::cout << "Inserted" << val << "!\n";
        else
            std::cout << "Coundn't be inserted!\n";

        bs.print();
    }

    return 0;
}