题目描述

小 B 按顺序记录同学们的比赛分数。每记录一个分数，就要公布当前记录中两个值：

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

某个值还不存在时，用 $0$ 表示。请在读入每个分数后，依次输出这两个值。分数都是正整数，所以 $0$ 不会与真实分数混淆。

输入格式

第一行一个整数 $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$。每个子任务的数据分别独立评测。