#include <cstring>
#include <vector>
#include <functional>

using namespace std;

template<class Type, const unsigned maxsize>
class stack
{
    private:
        Type s[maxsize];
        unsigned len;
    public:
        void push(Type t)
        {
            if (len == maxsize) return;
            s[len ++ ] = t;
        }

        Type top()
        {
            return s[len - 1];
        }

        void clear()
        {
            len = 0;
        }

        bool empty()
        {
            return !len;
        }

        void pop()
        {
            if (empty()) return;
            len -- ;
        }

        unsigned size()
        {
            return len;
        }

        stack()
        {
            len = 0;
        }

        stack(Type *a, unsigned l)
        {
            len = l;
            memcpy(s, a, l * sizeof(Type));
        }

        stack(vector<Type> a)
        {
            len = a.size();
            for (unsigned i = 0; i < len; i ++ ) s[i] = a[i];
        }

        stack(vector<Type> a, unsigned l, unsigned r)
        {
            len = r - l;
            for (unsigned i = 0; i < len; i ++ ) s[i] = a[i + l];
        }

        stack<Type, maxsize>(stack<Type, maxsize> &a)
        {
            memcpy(s, a.s, min(maxsize, a.len) * sizeof(Type));
            len = a.len;
        }
};

template<class Type, const unsigned maxsize, bool cmp(Type, Type) = greater<Type>()>
class heap
{
    private:
        Type h[maxsize];
        unsigned len = 0;
    public:
        void push(Type t)
        {
            if (len == maxsize) return;
            unsigned i;
            h[i = len ++ ] = t;
            while (i)
            {
                int f = i - 1 >> 1;
                if (cmp(h[i], h[f])) break;
                swap(h[i], h[f]);
                i = f;
            }
        }

        Type top()
        {
            return h[0];
        }

        unsigned size()
        {
            return len;
        }

        bool empty()
        {
            return len;
        }

        void pop()
        {
            if (empty()) return;
            Type t = h[0];
            h[0] = h[ -- len];
            unsigned i = 0;
            while (i << 1 < len - 1)
            {
                if (i << 1 < len - 2 && h[(i << 1) + 1] < h[i + 1 << 1])
                {
                    swap(h[i], h[i + 1 << 1]);
                    i = i + 1 << 1;
                }
                else
                {
                    swap(h[i], h[(i << 1) + 1]);
                    i = (i << 1) + 1;
                }
            }
        }

        void clear()
        {
            len = 0;
        }

        heap()
        {

        }

        heap(Type *a, int l)
        {
            for (unsigned i = 0; i < l; i ++ ) push(a[i]);
        }

        heap(vector<Type> a)
        {
            for (Type t : a) push(t);
        }

        heap(vector<Type> a, unsigned l, unsigned r)
        {
            for (unsigned i = l; i < r; i ++ ) push(a[i]);
        }

        heap<Type, maxsize, cmp>(heap<Type, maxsize, cmp> &a)
        {
            memcpy(h, a.h, min(maxsize, a.len) * sizeof(Type));
            len = a.len;
        }
};

template<class Type, const unsigned maxsize, bool cmp(Type, Type) = less<Type>()>
class min_stack
{
    private:
        Type s[maxsize], m[maxsize];
        unsigned len = 0;
    public:
        void push(Type t)
        {
            if (len == maxsize) return;
            s[len] = t;
            if (!len) m[len] = t;
            else m[len] = (m[len - 1] ? cmp(m[len - 1], t) : t);
            len ++ ;
        }

        Type top()
        {
            return s[len - 1];
        }

        unsigned size()
        {
            return len;
        }

        bool empty()
        {
            return len;
        }

        void clear()
        {
            len = 0;
        }

        void pop()
        {
            if (!len) return;
            len -- ;
        }

        Type min()
        {
            return m[len - 1];
        }

        min_stack()
        {

        }

        min_stack(Type *a, unsigned l)
        {
            for (unsigned i = 0; i < l; i ++ ) push(a[i]);
        }

        min_stack(vector<Type> a)
        {
            for (Type t : a) push(t);
        }

        min_stack(vector<Type> a, unsigned l, unsigned r)
        {
            for (unsigned i = l; i < r; i ++ ) push(a[i]);
        }

        min_stack<Type, maxsize, cmp>(min_stack<Type, maxsize, cmp> &a)
        {
            memcpy(s, a.s, min(maxsize, a.len) * sizeof(Type));
            memcpy(m, a.m, min(maxsize, a.len) * sizeof(Type));
            len = a.len;
        }
};