#include <cmath>
#include <map>
#include <string>
#include <algorithm>
#include <iostream>
#include <set>
#include <utility>
#include <vector>
#include <numeric>
#include <chrono>
#include <type_traits>
#include <cassert>
#include <sstream>
#include <unordered_map>
#include <stdexcept>
#include <stack>
#include <iterator>
#include <iomanip>
using namespace std;

template <typename Type>
struct PairWithMin{
    Type element;
    Type minimum;
};

template <typename Type>
ostream &operator<<(ostream &out, const PairWithMin<Type> &pair_to_print){
    // будем выводить только сам элемент, выводить минимум не будем
    out << pair_to_print.element;
    return out;
}

template <typename It>
void PrintRange(It range_begin, It range_end){
    for(auto it = range_begin; it != range_end; ++it){
        cout << *it << " "s;
    }
    cout << endl;
}

template <typename Type>
class Stack{
public:
    void Push(const Type &element){ //Вставка элемента в стек
        elements_.push_back(element);
    }
    void Pop(){ //Удаление элемента из стека
        elements_.pop_back();
    }
    const Type &Peek() const{ //Получение значения вершины стека
        /*const Type type;
        for(size_t i = 0; i < elements_.size(); ++i){
            if(elements_.at(i) == elements_.size() - 1){
                type = elements_.at(i);
            }
        }
        return type;*/
        //return elements_[static_cast<int>(elements_.size()) - 1];
        return elements_.back();
    }
    Type &Peek(){ //Получение значения вершины стека
        /*Type type;
        for(size_t i = 0; i < elements_.size(); ++i){
            if(elements_.at(i) == elements_.size() - 1){
                type = elements_.at(i);
            }
        }
        return type;*/
        //return elements_[static_cast<int>(elements_.size()) - 1];
        return elements_.back();
    }
    void Print() const{ // вывод в консоль
        PrintRange(elements_.begin(), elements_.end());
    }
    uint64_t Size() const{ //Размер стека — Size
        //return static_cast<uint64_t>(elements_.size());
        return elements_.size();
    }
    bool IsEmpty() const{ //Проверка на пустоту
        return elements_.empty();
    }
    const Type &Front() const{
        return elements_.front();
    }
    Type &Front(){
        return elements_.front();
    }
    ~Stack(){};
private:
    vector<Type> elements_;
};

template <typename Type>
class StackMin{
public:
    void Push(const Type &element){
        /*if(!minimum_.IsEmpty()){
            if(element > minimum_.Front().second){
                minimum_.Push({element, minimum_.Front().second});
            }
        } else{
            minimum_.Push({element,element});
        }*/
//_________________________________________________________________
        PairWithMin<Type> new_pair = {element, element};
        // проверим, что должно стать минимумом для текущего элемента -
        // он сам, или предыдущий минимум
        if(!minimum_.IsEmpty() && new_pair.minimum > minimum_.Peek().minimum){
            new_pair.minimum = minimum_.Peek().minimum;
        }
        // положим структуру в стек
        minimum_.Push(new_pair);
    }
    void Pop(){
        if(minimum_.Size() != 0){
            minimum_.Pop();
        }
    }
    const Type &Peek() const{
        return minimum_.Peek().element;
    }
    Type &Peek(){
        return minimum_.Peek().element;
    }
    void Print() const{
        minimum_.Print();
    }
    uint64_t Size() const{
        return minimum_.Size();
    }
    bool IsEmpty() const{
        return minimum_.IsEmpty();
    }
    const Type PeekMin() const{
        return minimum_.Peek().minimum;
    }
    Type PeekMin(){
        return minimum_.Peek().minimum;
    }
    ~StackMin(){};
private:
    Stack<PairWithMin<Type>> minimum_;
};

template <typename Type>
class SortedSack{
public:
    void Push(const Type &element){
        if(!elements_.IsEmpty()){
            if(element <= elements_.Peek()){
                elements_.Push(element);
            } else{
                //elements_.Push(elements_.Front());
                elements_.Push(elements_.Peek());
                //elements_.Push(element);
            }
        } else{
            elements_.Push(element);
        }
        for(size_t i = 0; i < elements_.Size(); i++){
            if(elements_.Peek() <= element){
                elements_.Pop();
                elements_.Push(element);
            }
        }
    }
    void Pop(){
        elements_.Pop();
    }
    const Type &Peek() const{
        return elements_.Peek();
    }
    Type &Peek(){
        return elements_.Peek();
    }
    void Print() const{
        elements_.Print();
    }
    uint64_t Size() const{
        return elements_.Size();
    }
    bool IsEmpty() const{
        return elements_.IsEmpty();
    }
    ~SortedSack(){};
private:
    Stack<Type> elements_;
};

int main(){
    setlocale(LC_ALL, "");
    SortedSack<int> sack;
    vector<int> values(5);

    // заполняем вектор для тестирования нашего класса
    iota(values.begin(), values.end(), 1);
    // перемешиваем значения
    random_shuffle(values.begin(), values.end());

    // заполняем класс и проверяем, что сортировка сохраняется после каждой вставки
    for(int i = 0; i < 5; ++i){
        cout << "Вставляемый элемент = "s << values[i] << endl;
        sack.Push(values[i]);
        sack.Print();
    }
}