### 问题描述 贝贝有一个大小为 $n$ 的可重集合 $\{2^{a_1},2^{a_2},\cdots,2^{a_n}\}$， * 可重集合，即集合中的数允许出现多次。 约定一次操作的过程如下： * 第一步，从集合中取出两个数并从集合中删除，约定较小的为 $x$，较大的为 $y$，即 $x\le y$； * 第二步，将 $2x$ 插入集合中； * 第三步，若 $y\ne x$，则将 $y-x$ 插入集合中。 贝贝想知道，经过若干次操作后，集合的大小**最小**可以为多少？ ### 输入格式 第一行，包含一个整数 $n(1\le n\le 10^5)$。 第二行，包含 $n$ 个整数 $a_1,a_2,\cdots,a_n(1\le a_i\le 10^9)$。 ### 输出格式 仅一行，包含一个整数，表示经过若干次操作后，集合的大小的最小值。 ### 样例输入 ``` 5 1 1 1 3 1 ``` ### 样例输出 ``` 1 ``` ### 说明 一种贝贝可能的操作顺序如下： 第一次操作，取出 $2^1,2^1$，操作完毕后集合变成 $\{2^1,2^1,2^2,2^3\}$。 第二次操作，取出 $2^1,2^1$，操作完毕后集合变成 $\{2^2,2^2,2^3\}$。 第三次操作，取出 $2^2,2^2$，操作完毕后集合变成 $\{2^3,2^3\}$。 第四次操作，取出 $2^3,2^3$，操作完毕后集合变成 $\{2^4\}$。 故最终集合大小的最小值为 $1$。