#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 RandomIt>
void random_shuffle(RandomIt first, RandomIt last){
    typename iterator_traits<RandomIt>::difference_type i, n;
    n = last - first;
    for(i = n - 1; i > 0; --i){
        swap(first[i], first[rand() % (i + 1)]);
    }
}

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

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{return elements_.back();}
    //Получение значения вершины стека
    Type &Peek(){return elements_.back();}
    // вывод в консоль
    void Print() const{ PrintRange(elements_.begin(), elements_.end());}
    //Размер стека — Size
    uint64_t Size() const{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(){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 SortedStack{
public:
    void Push(const Type &element){
        if(elements_.IsEmpty()){
            elements_.Push(element);
            return;
        }
        Type last_elem = elements_.Peek();
        if(last_elem < element){
            elements_.Pop();
            Push(element);
            elements_.Push(last_elem);
        }else{
            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();}
    ~SortedStack(){};
private:
    Stack<Type> elements_;
};

template <typename Type>
class Queue{
public:
    void Push(const Type &element){
        //if(stack1_.empty()){
            stack1_.push(element);
       //     return;
       // }
    }
    //void Pop(){
    //    if(!stack1_.empty()){
    //        Type last_elem = stack1_.top();
    //        if(last_elem < stack2_.top()){
    //            //stack1_.pop();
    //            //Push(last_elem);
    //            stack2_.push(last_elem);
    //        } else{
    //            stack1_.push(stack2_.top());
    //        }
    //    }
    //    /*if(stack2_.empty()){
    //        while(!stack1_.empty()){
    //            Type last_elem = stack1_.top();
    //            stack1_.pop();
    //            stack2_.push(last_elem);
    //        }
    //    }*/
    //}
    void Pop(){
        if(stack2_.empty()){
            while(!stack1_.empty()){
                stack2_.push(stack1_.top());
                stack1_.pop();
            }
        }
        stack2_.pop();
    }
    Type &Front(){
        if(stack2_.empty()){
            while(!stack1_.empty()){
                stack2_.push(stack1_.top());
                stack1_.pop();
            }
        }
        return stack2_.top();
    }
    uint64_t Size() const{return stack1_.size() + stack2_.size();}
    bool IsEmpty() const{return stack1_.empty() && stack2_.empty();}

private:
    stack<Type> stack1_;
    stack<Type> stack2_;
};