题目描述

小明最近在研究压缩算法。

他知道，压缩的时候如果能够使得数值很小，就能通过熵编码得到较高的压缩比。

然而，要使数值很小是一个挑战。

最近，小明需要压缩一些正整数的序列，这些序列的特点是，后面出现的数字很大可能是刚出现过不久的数字。对于这种特殊的序列，小明准备对序列做一个变换来减小数字的值。

变换的过程如下：

从左到右枚举序列，每枚举到一个数字，如果这个数字没有出现过，刚将数字变换成它的相反数，如果数字出现过，则看它在原序列中最后的一次出现后面（且在当前数前面）出现了几种数字，用这个种类数替换原来的数字。

比如，序列 $(a_1,a_2,a_3,a_4,a_5)=(1, 2, 2, 1, 2)$ 在变换过程为：

$a_1$ : 1 未出现过，所以 $a_1$ 变为 -1；

$a_2$ : 2 未出现过，所以 $a_2$ 变为 -2；

$a_3$ : 2 出现过，最后一次为原序列的 $a_2$ ，在 $a_2$ 后、 $a_3$ 前有 0 种数字，所以 $a_3$ 变为 0；

$a_4$ : 1 出现过，最后一次为原序列的 $a_1$ ，在 $a_1$ 后、 $a_4$ 前有 1 种数字，所以 $a_4$ 变为 1；

$a_5$ : 2 出现过，最后一次为原序列的 $a_3$ ，在 $a_3$ 后、 $a_5$ 前有 1 种数字，所以 $a_5$ 变为 1。

现在，给出原序列，请问，按这种变换规则变换后的序列是什么。

输入描述

输入第一行包含一个整数 $n$ ，表示序列的长度。

第二行包含 $n$ 个正整数，表示输入序列。其中， $1≤n≤10^5，1≤a_i≤10^9$ 。

输出一行，包含 $n$ 个数，表示变换后的序列。

5
1 2 2 1 2

-1 -2 0 1 1