#include <bits/stdc++.h>
using namespace std;
struct P {
int value;
int accumulated;
};
stack<P> A, B;
P merge(P x, P y){ // x is on top of y
x.accumulated = max(x.accumulated, y.accumulated);
return x;
}
void push(int value){
P element;
element.value = element.accumulated = value;
if(!B.empty())
element = merge(element, B.top());
B.push(element);
}
void pop(){
if(A.empty()){
while(!B.empty()){
P element = B.top();
B.pop();
element.accumulated = element.value;
if(!A.empty())
element = merge(element, A.top());
A.push(element);
}
}
A.pop();
}
int get_max(){
int mx = -(1<<30);
if(!A.empty())
mx = max(mx, A.top().accumulated);
if(!B.empty())
mx = max(mx, B.top().accumulated);
return mx;
}
int main() {
push(7);
push(5);
cout << get_max() << '\n';
pop();
cout << get_max() << '\n';
push(12);
cout << get_max() << '\n';
pop();
cout << get_max() << '\n';
pop();
push(13);
push(15);
pop();
push(17);
cout << get_max() << '\n';
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0cnVjdCBQIHsKCWludCB2YWx1ZTsKCWludCBhY2N1bXVsYXRlZDsKfTsKc3RhY2s8UD4gQSwgQjsKUCBtZXJnZShQIHgsIFAgeSl7IC8vIHggaXMgb24gdG9wIG9mIHkKCXguYWNjdW11bGF0ZWQgPSBtYXgoeC5hY2N1bXVsYXRlZCwgeS5hY2N1bXVsYXRlZCk7CglyZXR1cm4geDsKfQp2b2lkIHB1c2goaW50IHZhbHVlKXsKCVAgZWxlbWVudDsKCWVsZW1lbnQudmFsdWUgPSBlbGVtZW50LmFjY3VtdWxhdGVkID0gdmFsdWU7CglpZighQi5lbXB0eSgpKQoJCWVsZW1lbnQgPSBtZXJnZShlbGVtZW50LCBCLnRvcCgpKTsKCUIucHVzaChlbGVtZW50KTsKfQp2b2lkIHBvcCgpewoJaWYoQS5lbXB0eSgpKXsKCQl3aGlsZSghQi5lbXB0eSgpKXsKCQkJUCBlbGVtZW50ID0gQi50b3AoKTsKCQkJQi5wb3AoKTsKCQkJZWxlbWVudC5hY2N1bXVsYXRlZCA9IGVsZW1lbnQudmFsdWU7CgkJCWlmKCFBLmVtcHR5KCkpCgkJCQllbGVtZW50ID0gbWVyZ2UoZWxlbWVudCwgQS50b3AoKSk7CgkJCUEucHVzaChlbGVtZW50KTsKCQl9Cgl9CglBLnBvcCgpOwp9CmludCBnZXRfbWF4KCl7CglpbnQgbXggPSAtKDE8PDMwKTsKCWlmKCFBLmVtcHR5KCkpCgkJbXggPSBtYXgobXgsIEEudG9wKCkuYWNjdW11bGF0ZWQpOwoJaWYoIUIuZW1wdHkoKSkKCQlteCA9IG1heChteCwgQi50b3AoKS5hY2N1bXVsYXRlZCk7CglyZXR1cm4gbXg7Cn0KaW50IG1haW4oKSB7CglwdXNoKDcpOwoJcHVzaCg1KTsKCWNvdXQgPDwgZ2V0X21heCgpIDw8ICdcbic7Cglwb3AoKTsKCWNvdXQgPDwgZ2V0X21heCgpIDw8ICdcbic7CglwdXNoKDEyKTsKCWNvdXQgPDwgZ2V0X21heCgpIDw8ICdcbic7Cglwb3AoKTsKCWNvdXQgPDwgZ2V0X21heCgpIDw8ICdcbic7Cglwb3AoKTsKCXB1c2goMTMpOwoJcHVzaCgxNSk7Cglwb3AoKTsKCXB1c2goMTcpOwoJY291dCA8PCBnZXRfbWF4KCkgPDwgJ1xuJzsKCXJldHVybiAwOwp9