Problem F: 在栈当中实现O(1)级别的min 函数

Problem F: 在栈当中实现O(1)级别的min 函数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 47  Solved: 41
[Submit][Status][Web Board][Creator:]

Description

提示:所谓O(1)是指无论栈多大,求最小值只需要一次操作,而不需要循环整个栈。

方法1:每次进栈除了进数据本身,还将最新的最小值进栈,每次出栈也是出两个;

方法2:构造一个最小栈存放不断变化的最小值,如果新的数据小于等于最小值则进最小栈。

Input

依次输入多个正整数,以-1为终止标记


Output

第一行:每进一个数之后,输出当前的最小值;

第二行:全部进完之后再依次出栈,每出一个数之后输出当前的最小值,如栈已空则停止输出。

所有输出用空格分割。

Sample Input

2 2 3 2 1 -1

Sample Output

2 2 2 2 1 
2 2 2 2 
[Submit][Status]