题目描述

离开平原后，小 A 来到一座村庄。村口的告示牌上挂着一份积分榜，村民会按顺序记下每一位玩家的得分。为了让大家随时知道自己排在第几档，每记录一个分数，告示牌就要立刻公布当前记录中的两个值：

1. 第二大分数：把已经记录的每个分数都看成独立的一份，从大到小排列后排第二的值。因此，若最高分出现了两次，第二大分数也等于最高分。
2. 严格第二大分数：在所有小于最高分的分数中取最大的值。

某个值还不存在时，用 $0$ 表示。因为分数都是正整数，所以 $0$ 不会与真实分数混淆。

现在给出村民记录的 $n$ 个分数，请你帮小 A 依次算出每记下一个分数后，告示牌应公布的两个值。

输入格式

第一行一个整数 $n$，表示记录的分数个数。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示记录顺序。

输出格式

输出 $n$ 行。第 $i$ 行两个整数，分别是前 $i$ 个分数中的第二大分数与严格第二大分数。

样例

6
5 9 9 3 12 12

0 0
5 5
9 5
9 5
9 9
12 9

3
7 7 7

0 0
7 0
7 0

4
10 4 8 20

0 0
4 4
8 8
10 10

样例解释

• 样例 1：读到第二个 $9$ 时，最高分有两份，故第二大为 $9$，严格第二大仍为 $5$；读到第一个 $12$ 后，原最高分 $9$ 成为严格第二大。
• 样例 2：三个分数都相等，因此始终不存在严格第二大。
• 样例 3：最后读到 $20$ 时，旧最高分 $10$ 同时成为两个值。

数据范围与约定

对于 $100\%$ 的数据，$2\le n\le10^5$，$1\le a_i\le10^9$。每个子任务的数据分别独立评测。