C - Bacteria

　

bacteria

添加链接描述

recently Monocarp has created his own Mini-laboratory!

The laboratory contains $$n$n$ bacteria. Monocarp knows that he can merge any two bacteria having equal sizes, and the resulting bacterium will have the size equal to the sum of sizes of merged bacteria. For example, if two bacteria having sizes equal to $$7$7$ merge, one bacterium with size $$14$14$ is the result.

It becomes hard to watch for many bacteria, so Monocarp wants to merge all of them into one bacterium. It may not be possible to do this with the bacteria Monocarp has, so he can buy any number of bacteria of any possible integer sizes in a special store.

You have to determine the minimum number of bacteria Monocarp has to buy to merge them with the $$n$n$ bacteria his laboratory contains into exactly one bacterium.

Input

The first line contains one integer $$n$n$ $$(1\le n\le 2\cdot 10^5)$(1≤n≤2⋅105)$ — the number of bacteria Monocarp’s laboratory contains.

The second line contains $$n$n$ integers $$a_1,a_2,\dots ,a_n$a1​,a2​,…,an​$ $$(1\le a_i\le 10^9)$(1≤ai​≤109)$, where $$a_i$ai​$ is the size of the $$i$i$-th bacterium in the laboratory.

Output

If it is impossible to merge the bacteria (possibly after buying some) into only one bacterium, print -1.

Otherwise print the minimum number of bacteria Monocarp has to buy to merge them with the $$n$n$ bacteria his laboratory contains into exactly one bacterium.

Examples

Input

2

1 4

Output

2

Input

3

3 6 9

Output

-1

Input

7

1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Output

1

Note

In the first example Monocarp should buy one bacterium having size $$1$1$ and one bacterium having size $$2$2$. Then Monocarp will have $$4$4$ bacteria having sizes $$[1,4,1,2]$[1,4,1,2]$. Then two bacteria having sizes $$1$1$ can be merged into one having size $$2$2$. Then Monocarp will have $$3$3$ bacteria having sizes $$[2,4,2]$[2,4,2]$. Then two bacteria having sizes $$2$2$ can be merged into one having size $$4$4$. Then Monocarp will have $$2$2$ bacteria having sizes $$[4,4]$[4,4]$, which can be merged into one having size $$8$8$.

In the second example no matter which bacteria Monocarp will buy, he cannot merge all his bacteria.

In the third example Monocarp needs to buy one bacterium having size $$1000000000$1000000000$.

思路：每次取出最小和次小的元素x1，x2，如果x1=x2，删掉这两个元素，把x1+x2入队列，如果x1不等于x2,把最小的元素删除，再把x1*2加到队列里面（相当于加了一个元素x1，把两个x1合并），直到队列只剩一个元素（说明可能实现把所有元素归到一个上），如果队列里元素一直大于一个，说明无法把所有元素归到一个上。

用到优先队列

头文件#include

priority_queue<int,vector,greater >

priority_queue里面一共有三个参数，第一个是队列元素的类型，第二个是容器，第三个队列元素的排序方法。

greater 表示从小往大排，less表示从大向小排

另外，最后的两个> > 要隔开，不能连在一起写成>>,>>表示一种移位符

详解添加链接描述

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()

{

ll n;
while(~scanf("%lld",&n))
{
    priority_queue<ll, vector<ll>, greater<ll> > q;
    ll x;
    for(int i = 0; i < n; i ++)
    {
        scanf("%lld", &x);
        q.push(x);
    }
    ll cnt = 0;
    ll x1, x2;
    ll f = 0;
    if(n == 1) {printf("0\n");continue;}
    while(!q.empty())
    {
        x1 = q.top();
        q.pop();
        if(!q.empty())
        {
            x2 = q.top();
            if(x1 == x2)
            {
                x1 = x1 + x2;
                q.pop();
                q.push(x1);
            }
            else {
                x1 = 2 * x1;
                q.push(x1);
                cnt ++;
            }
        }
        else {
            break;
        }
        if(cnt > 3e5) {f = 1;break;}
    }
    if(f==0)printf("%lld\n",cnt);
    else printf("-1\n");
}
return 0;

}

相关阅读