链接: https://cses.fi/problemset/task/2425

板块: Additional Problems I

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你有 $n$ 枚硬币，每枚硬币的重量都不同。

有两个初始为空的栈。每一步你将一枚硬币移到某个栈中。你永远不会从栈中拿走硬币。

每次移动后，你的任务是判断哪个栈更重（如果我们能确定某个栈更重的话）。

输入

第一行输入包含一个整数 $n$：硬币的数量。硬币编号为 $1,2,\dots,n$。你知道硬币 $i$ 总是比硬币 $i-1$ 重，但不知道它们的确切重量。

接下来有 $n$ 行描述移动。每行有两个整数 $c$ 和 $s$：将硬币 $c$ 移到栈 $s$（$1$ = 左，$2$ = 右）。

输出

每次移动后，如果右栈更重则输出 <，如果左栈更重则输出 >，如果无法确定哪个栈更重则输出 ?。

数据范围

$1 \le n \le 2 \cdot 10^5$

样例输入

3
2 1
3 2
1 1

样例输出

>
<
?