Определение минимального элемента в очереди за константное время

Структура данных очередь используется во многих алгоритмах. Помимо стандартных операций иногда существует необходимость в получении минимального (максимального) элемента за константное время. Поддержка такой статистики со стеком реализуется тривиально - вместе с добавленным элементом сохраняется минимум всех элементов на стеке (рассчитывается как минимум из добавленного элемента и значения минимума предыдущих значений на стеке). Этот подход адаптируется и для очереди. Как известно очередь можно реализовать с помощью двух стеков: стек для добавления элементов S1 и стек для изъятия элементов S2. Т.е. любое добавление в очередь добавляет элемент в S1, а любое изъятие проверяет стек S2 и если он пустой, то  перекладывает все элементы из S1 в S2. После этого извлекает элемент с вершины стека S2. Т.о. реализовав очередь с помощью двух стеков с поддержкой минимального элемента, мы в любой момент можем получить минимум в очереди как минимум минимальных элементов стека S1 и S2.

#define ZERO (1LL<<60)
#define ADD(x, y) (min((x), (y)))

typedef pair<lint, lint> plii;
typedef long long lint;

const int MAX = 1000000 + 10;

struct Queue {
    
    plii v1[MAX], v2[MAX];
    int n1, n2;
    
    Queue() {
        clear();
    }
    
    void push(lint x) {
        v1[n1] = mp(x, ADD(x, v1[n1 - 1].second));
        n1++;
    }
    
    void pop() {
        if (n2 == 1) {
            while (n1 > 1) {
                lint x = v1[--n1].first;
                v2[n2] = mp(x, ADD(x, v2[n2 - 1].second));
                n2++;
            }
        }
        n2--;
    }
    
    lint get() {
        return ADD(v1[n1 - 1].second, v2[n2 - 1].second);
    }
    
    int size() {
        return n1 + n2 - 2;
    }
    
    void clear() {
        n1 = n2 = 0;
        v1[n1++] = mp(ZERO, ZERO);
        v2[n2++] = mp(ZERO, ZERO);
    }
};

Данная структура данных применяется в следующих задачах:
- рюкзак с ограничением количества элементов. Позволяет решить задачу за O(NW)
- поиск минимума во всевозможных диапозонах массива фиксированной длины (скользящее окно по массиву)