问题描述

有一个空的队列和 $N$ 个球。第 $i$ 个球（$1 \leq i \leq N$）的大小为 $2^{A_i}$。

接下来按顺序进行 $N$ 次操作。在第 $i$ 次操作中，将第 $i$ 个球加入队列的最右端，然后重复以下步骤：

1. 如果队列中的球数不超过 $1$，则结束本次操作；
2. 如果队列中从右数第 $1$ 个和第 $2$ 个球的大小不同，则结束本次操作；
3. 如果队列中从右数第 $1$ 个和第 $2$ 个球的大小相同，则将这两个球移除，并在队列最右端加入一个大小为“被移除的两个球大小之和”的新球。之后回到步骤 1，继续重复检查。

请在 $N$ 次操作全部结束后，输出队列中剩余球的数量。

输入格式

第一行输入一个整数 $N$，表示球的数量。

第二行输入 $N$ 个整数 $A_1, A_2, \ldots, A_N$。

输出格式

输出一个整数，表示 $N$ 次操作结束后队列中剩余球的数量。

样例输入 1

7
2 1 1 3 5 3 3

样例输出 1

3

样例输入 2

5
0 0 0 1 2

样例输出 2

4

说明

样例 1 解释：

• 第 $1$ 次操作后，队列中为 $[2^2]$，共 $1$ 个球；
• 第 $2$ 次操作后，队列中为 $[2^2, 2^1]$，共 $2$ 个球；
• 第 $3$ 次操作后：
  • 加入第 $3$ 个球后队列为 $[2^2, 2^1, 2^1]$；
  • 最右侧两球大小相同，合并为 $2^1 + 2^1 = 2^2$，此时队列为 $[2^2, 2^2]$；
  • 再次发现最右侧两球大小相同，合并为 $2^2 + 2^2 = 2^3$，此时队列为 $[2^3]$，共 $1$ 个球；
• 第 $4$ 次操作后，加入 $2^3$，与栈顶 $2^3$ 合并为 $2^4$，队列为 $[2^4]$，共 $1$ 个球；
• 第 $5$ 次操作后，队列为 $[2^4, 2^5]$，共 $2$ 个球；
• 第 $6$ 次操作后，队列为 $[2^4, 2^5, 2^3]$，共 $3$ 个球；
• 第 $7$ 次操作后，队列为 $[2^4, 2^5, 2^4]$，共 $3$ 个球。

最终队列中剩余 $3$ 个球。

评测数据规模

对于所有评测数据：

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq A_i \leq 10^9 \quad (1 \leq i \leq N)$
• 所有输入均为整数