#CS2425. 堆叠硬币

堆叠硬币

题目背景

翻译自 CSES-2425 题。

题目描述

你有 n 个硬币，每个硬币的重量不同。

有两个堆栈，初始时它们都是空的。在每一步，你将一个硬币移到一个堆栈中。你从不移除堆栈中的硬币。

在每次操作后，你的任务是确定哪个堆栈更重（如果能够确定某个堆栈更重的话）。

输入格式

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

接下来有 n 行，每行包含两个整数 c 和 s，表示将硬币 c 移到堆栈 s（s=1s=1s=1 表示左堆栈，s=2s=2s=2 表示右堆栈）。

输出格式

对于每次操作，输出：

• 如果右堆栈更重，输出 <；

• 如果左堆栈更重，输出 >；

• 如果无法确定哪个堆栈更重，输出 ?。

样例

3
2 1
3 2
1 1

>
<
?

样例1解释 在最后一次操作后，如果硬币的分布是 [2,3,4][2, 3, 4][2,3,4]，则左堆栈更重，但如果硬币的分布是 [1,2,5][1, 2, 5][1,2,5]，则右堆栈更重。

说明/提示

$1 \leq n \leq 2 \times 10^5$