题目描述

有 $n$ 名士兵参加了一场激烈的战斗。每个士兵身边有两个 伙伴，第 $i$ 号士兵的 左侧伙伴 编号为 $i−1$， 右侧伙伴 的编号为 $i+1$。$1$ 号士兵没有 左侧伙伴，$n$ 号士兵没有 右侧伙伴。

在战斗过程中，陆续牺牲了 $m$ 名士兵。一旦一名士兵牺牲了，存活的士兵就会相互接近，形成新的 伙伴 关系。给定士兵们牺牲的顺序及编号，请你输出当每个士兵牺牲时，新构成 伙伴 关系的两个士兵的编号。

输入格式

第一行：两个正整数表示 $n$ 和 $m$。 第二行到第 $m+1$ 行：在第 $i+1$ 行，有一个正整数 $s_i$，表示第 $i$ 个牺牲的士兵编号。

输出格式

共 $m$ 行：每行两个整数，第 $i$ 行表示当 $s_i$ 牺牲时，左右 伙伴 的编号，如果某侧没有 伙伴，输出一个 *。

样例

5 3
3
2
1

2 4
1 4
* 4

数据范围

• 对于 $30\%$ 的测试数据满足：$1≤n≤10000$。
• 对于 $60\%$ 的测试数据满足：$1≤n≤100000$。
• 对于 $100\%$ 的测试数据满足：$1≤n≤1000000,1≤m<n$。
• 本题数据范围很大，请尽量优化代码的时间消耗。
• 在这题中，尽量不要使用 endl 进行换行，否则可能会导致你的代码 TLE。