#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>
using namespace std;

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();
    }

private:
    vector<Type> elements_;
};

template <typename Type>
class StackMin{
public:
    void Push(const Type &element){
        elements_.Push(element);
        //minimum_[element].push_back(elements_.Peek());
        for(int i = 0; i < elements_.Size(); i++){
            minimum_[i] = i - 1;
            while(minimum_[i] >= 0 && elements_[minimum_[i]] >= elements_[i]){
                minimum_[i] = minimum_[minimum_[i]];
            }
        }
    }
    void Pop(){
        elements_.Pop();
        /*auto elem = elements_.Peek();
        minimum_[elem].pop_back();
        if(minimum_[elem].size() == 0){
            minimum_.erase(elem);
        }
        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();
    }
    const Type &PeekMin() const{
        //const auto min = minimum_.begin();
        //return minimum_[min].front();
        return elements_.Peek();
    }
    Type &PeekMin(){
        //auto min = minimum_.begin();
        //return minimum_[min].front();
        return elements_.Peek();
    }
private:
    Stack<Type> elements_;
    vector<pair<Type,Type>> minimum_;
};
int main(){
    setlocale(LC_ALL, "");
    stack<int> stacks;
    StackMin<int> stack;
    vector<int> values(5);
    // заполняем вектор для тестирования нашего стека
    iota(values.begin(), values.end(), 1);
    // перемешиваем значения
    //random_shuffle(values.begin(), values.end());
    // заполняем стек
    for(int i = 0; i < 5; ++i){
        stack.Push(values[i]);
    }
    // печатаем стек и его минимум, постепенно убирая из стека элементы
    while(!stack.IsEmpty()){
        stack.Print();
        cout << "Минимум = "s << stack.PeekMin() << endl;
        stack.Pop();
    }
}