#include <bits/stdc++.
h>
using namespace std;
#define F first
#define S second
/**
* Monotonic queue to keep track of the minimum and/or the maximum
* elements so far in the queue in O(1).
*/
template<class T>
class monotonic_queue {
stack<pair<T, pair<T, T>>> s1, s2;
void add(stack<pair<T, pair<T, T>>>& s, T v) {
T mx = std::max(v, [Link]().S.F);
T mn = std::min(v, [Link]().S.S);
[Link]({ v, { mx, mn } });
}
void flip() {
if ([Link]() > 1) {
return;
}
while ([Link]() > 1) {
add(s2, [Link]().F);
[Link]();
}
}
public:
/**
* Constructs a new monotonic queue.
*/
monotonic_queue() {
[Link]({ numeric_limits<T>::min(), { numeric_limits<T>::min(),
numeric_limits<T>::max() } });
[Link]({ numeric_limits<T>::min(), { numeric_limits<T>::min(),
numeric_limits<T>::max() } });
}
/**
* Pushes a new element to the end of this queue.
*
* @param v the new element to be pushed.
*/
void push(T v) {
add(s1, v);
}
/**
* Pops the front element from the queue.
* If the queue is empty, an exception is thrown.
*/
void pop() {
flip();
[Link]();
}
/**
* @return the front element of the queue.
*/
T front() const {
flip();
return [Link]().F;
}
/**
* @return the maximum element of the queue.
*/
T max() const {
return std::max([Link]().S.F, [Link]().S.F);
}
/**
* @return the minimum element of the queue.
*/
T min() const {
return std::min([Link]().S.S, [Link]().S.S);
}
/**
* @return the size of the queue.
*/
size_t size() const {
return [Link]() + [Link]() - 2;
}
};
