‹ 上一题 下一题 ›

g5-08216. 随时要最小值的栈 未做

1000 ms 256 MB 测试点 10 通过率 100% GESP-55级·STLstack

题目描述

维护一个初始为空的栈,依次处理 个操作:

  • 1 x:把整数 push 进栈;
  • 2:pop 弹出栈顶(数据保证此时栈非空);
  • 3:询问当前栈内所有数中的最小值并输出一行;若此时栈是空的,输出 。

只记一个「当前最小值」的变量活不过 pop:把最小值弹掉之后,剩下的数里的最小值就找不回来了。让一个辅助栈和主栈同步生长,辅助栈顶永远存「当前主栈里的最小值」。

输入格式

第一行一个整数 ()。

接下来 行,每行是一个操作,格式为 1 x、2 或 3;其中 。

输出格式

对每个操作 3,输出一行一个整数:当前栈内最小值,空栈时为 。

样例

输入:

5
1 5
1 1
3
2
3

输出:

1
5

第一次询问栈里是 5、1,最小是 1;弹出 1 后再问,栈里只剩 5。

数据范围

,。操作 2 保证栈非空;辅助栈与主栈同进同出,弹的时候一起弹。

输入
输出

            
答案