该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 n 名士兵参加了一场激烈的战斗。每个士兵身边有两个伙伴，第 i 号士兵的左侧伙伴编号为 i−1，右侧伙伴的编号为和 i+1。1 号士兵没有左侧伙伴，n 号士兵没有右侧伙伴。 在战斗过程中，陆续牺牲了 m 名士兵。一旦一名士兵牺牲了，存活的士兵就会相互接近，形成新的伙伴关系。给定士兵们牺牲的顺序及编号，请你输出当每个士兵牺牲时，新构成伙伴关系的两个士兵的编号。

输入格式

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

输出格式

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

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。