Varint 是一种用于使用一个或多个字节对整数进行序列化的类型。其核心思想是用较少的字节来编码较小的值。

首先，我们想要编码某个无符号整数 $x$。考虑其二进制表示 $x = a_0 a_1 a_2 \dots a_{k-1}$，其中 $a_i$ 表示第 $i$ 个有效位，即 $x = a_0 \cdot 2^0 + a_1 \cdot 2^1 + \dots + a_{k-1} \cdot 2^{k-1}$，而 $k-1$ 表示最高非零位的索引，若 $x = 0$ 则 $k = 1$。

为了编码 $x$，我们将使用 $m = \lceil \frac{k}{7} \rceil$ 个字节 $b_0, b_1, \dots, b_{m-1}$。这意味着对于 $0$ 到 $127$ 的整数使用一个字节，对于 $128$ 到 $2^{14} - 1 = 16383$ 的整数使用两个字节，依此类推，对于 $2^{64} - 1$ 最多使用十个字节。对于字节 $b_0, b_1, \dots, b_{m-2}$，其最高有效位（即第 7 位，从 0 开始计数）设为 1，而对于字节 $b_{m-1}$，其最高有效位设为 0。然后，对于每个从 $0$ 到 $k-1$ 的 $i$，字节 $b_{\lfloor \frac{i}{7} \rfloor}$ 的第 $i \bmod 7$ 位被设为 $a_i$。因此，

$$x = (b_0 - 128) \cdot 2^0 + (b_1 - 128) \cdot 2^7 + (b_2 - 128) \cdot 2^{14} + \dots + (b_{m-2} - 128) \cdot 2^{7 \cdot (m-2)} + b_{m-1} \cdot 2^{7 \cdot (m-1)}$$

在上述公式中，我们从 $b_0, b_1, \dots, b_{m-2}$ 中减去 128，因为它们的最高有效位被设为了 1。

例如，整数 7 将被表示为单个字节 $b_0 = 7$，而整数 260 将被表示为两个字节 $b_0 = 132$ 和 $b_1 = 2$。

为了表示有符号整数，我们引入了 ZigZag 编码。由于我们希望绝对值较小的整数具有较短的表示，我们将有符号整数映射到无符号整数，规则如下：整数 0 映射到 0，-1 映射到 1，1 映射到 2，-2 映射到 3，2 映射到 4，-3 映射到 5，3 映射到 6，依此类推，这也是该编码名称的由来。形式化地，如果 $x \ge 0$，它被映射到 $2x$；如果 $x < 0$，它被映射到 $-2x - 1$。

例如，整数 75 被映射到 150，并被编码为 $b_0 = 150, b_1 = 1$；而 -75 将被映射到 149，并被编码为 $b_0 = 149, b_1 = 1$。在本题中，我们仅考虑对范围在 $-2^{63}$ 到 $2^{63} - 1$（含两端）之间的整数进行此类编码。

给你一个字节序列，它对应于一系列被编码为 varint 的有符号整数。你的目标是解码并打印出原始的整数序列。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 10\,000$) —— 编码序列的长度（字节数）。

下一行包含 $n$ 个介于 0 到 255 之间的整数。你可以认为输入是合法的，即存在一个范围在 $-2^{63}$ 到 $2^{63} - 1$ 之间的整数序列，其被编码后恰好为输入中给出的字节序列。

输出格式

打印解码后的整数序列。

样例

输入样例 1

5
0 194 31 195 31

输出样例 1

0
2017
-2018