会当凌绝顶，一览众山小

题号：NC208378
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛最喜欢爬山了，他喜欢站在最高的山峰上展望。
牛牛来到山脚下，看到这里一共有 $n {}$ 个山峰，每个山峰有一个坐标 $x_i$ 和高度 $h_i$ （ $n{}$ 个山峰在一条直线上），参差不齐，心里瞬间很不舒服。他最喜欢看到的山峰是从左到右高度依次增大，所以牛牛就要使用魔法了。当牛牛登上第 $i{}$ 个山峰的时候，他要用乾坤大挪移把当前山峰左边( $x_j<x_i$ )第一个比这个山峰严格大的山峰变得和当前山峰一样高，如果右边( $x_j>x_i$ )没有山峰比他严格大，牛牛还是很不满足，他要把右边最小的山峰变成和当前山峰一样大（如果有多个最小的，变最左边的一个），当牛牛从第 $n{}$ 个山峰下来的时候，看到这一场面，心中很是满足，但是他不知道自己把山峰都变成什么样了，想要知道每个山峰的新高度 $h_i$ ,你能告诉他吗？
注意：登山顺序不一定从左到右，是按照给出山峰的顺序

输入描述:

第一行有一个正整数 $n（n \leq 2×10^5）$ ，表示有 $n{}$ 座山峰
接下来 $n{}$ 行每行有两个整数 $x ,h（10^{-9} \leq x\leq 10^9,1\leq h\leq 10^9）$
（保证每个 $x{}$ 都不相同）

输出描述:

输出一行， $n{}$ 个数，分别表示第 $i{}$ 个山峰最后的高度 $h{}$

示例1

输入

复制

输出

复制

3 3 3

说明

第一次登上坐标为2的山峰，右边没有比他高的，最小的是坐标3的山峰，所以坐标3的山峰变为3
左边第一个比他高的是坐标为1的山峰，也变为3
第二次登上坐标1的山峰，左边没有山峰，因为右边没有比他高的，但是最低的也和他一样高，所以改变后仍是3
第三次登上坐标3的山峰，右边没有山峰，左边没有比他高的不会改变
最终坐标2，1，3的高度分别对应为3，3，3