D1 - 单调栈

template< class type, class Comp >
class mono_stack {
	type ar[maxn + 1] {};
	int pos = 0;
	Comp cmp;
public:
	type push(type x) {
		while (!empty() && !cmp(top(), x)) pop();
		ar[++pos] = x;
		return pos == 1 ? -1 : ar[pos - 1];
	}
	bool empty() { return !pos; }
	type top() { return ar[pos]; }
	void pop() { --pos; }
};