魔法感应 Ⅳ

在遥远的佐希克大陆，充满着宗教与魔法，每个人都信仰着一个宗教，信仰相同宗教的人两两之间会产生魔法心灵感应。 现在有N个人站成一排，第i个人信仰的宗教为Ai。 大陆之主听到信徒们虔诚的祷告降临佐希克大陆，同时降下神威，导致本来可以相同宗教的人两两魔法感应，现在只能向左找到离着最近的相同宗教人产生魔法感应，也可以向右找到离着最近的相同宗教人产生魔法感应。 每对产生魔法感应的人，会对本信仰的宗教产生一个信仰贡献，信仰贡献值为这两个人之间的所有宗教数字之和（不包含这两个人）。 现在请你分别按从小到大的顺序求出每个宗教产生信仰贡献和是多少，如果某个宗教的信仰贡献为0，则不输出。如果所有宗教均没有信仰贡献，则输出“NONE”。

输入
第一行一个整数N，表示接下来有N个人。 接下来N行，每行一个整数Ai，表示第i个人信仰的宗教为Ai。 1 <= N <= 106; 1 <= Ai <= 106;

Output 输出若干行，每行两个整数，分别表示哪个宗教，对应的信仰贡献和，分别是多少。 如果所有宗教均没有产生信仰贡献值，则输出“NONE”。

Sample Input

10

3

2

5

4

2

6

1

3

5

2

Sample Output

2 24

3 20

5 16