題干：

Limak is a grizzly bear who desires power and adoration. He wants to win in upcoming elections and rule over the Bearland.

There are?n?candidates, including Limak. We know how many citizens are going to vote for each candidate. Now?i-th candidate would get?ai?votes. Limak is candidate number?1. To win in elections, he must get strictly more votes than any other candidate.

Victory is more important than everything else so Limak decided to cheat. He will steal votes from his opponents by bribing some citizens. To bribe a citizen, Limak must give him or her one candy - citizens are bears and bears like candies. Limak doesn't have many candies and wonders - how many citizens does he have to bribe?

Input

The first line contains single integer?n?(2?≤?n?≤?100) - number of candidates.

The second line contains?n?space-separated integers?a1,?a2,?...,?an?(1?≤?ai?≤?1000) - number of votes for each candidate. Limak is candidate number?1.

Note that after bribing number of votes for some candidate might be zero or might be greater than?1000.

Output

Print the minimum number of citizens Limak must bribe to have strictly more votes than any other candidate.

Examples

Input

5 5 1 11 2 8

Output

4

Input

4 1 8 8 8

Output

6

Input

2 7 6

Output

0

Note

In the first sample Limak has?5?votes. One of the ways to achieve victory is to bribe?4?citizens who want to vote for the third candidate. Then numbers of votes would be?9,?1,?7,?2,?8?(Limak would have?9?votes). Alternatively, Limak could steal only?3?votes from the third candidate and?1?vote from the second candidate to get situation?9,?0,?8,?2,?8.

In the second sample Limak will steal?2?votes from each candidate. Situation will be?7,?6,?6,?6.

In the third sample Limak is a winner without bribing any citizen.

題目大意：

? n個人參加選舉，現在知道目前n個人各自的得票數，現在要讓1號人獲勝（也就是1號的得票數嚴格大于其他人的得票數），問最少要賄賂幾個人？

解題報告：

? ? ?直接優先隊列可以搞出來。

AC代碼：

#include<bits/stdc++.h>using namespace std; priority_queue<int> pq; int main() {int n,ans=0,my,tmp;scanf("%d%d",&n,&my);//ans相當于a[1]for(int i = 2; i<=n; i++){scanf("%d",&tmp);if(tmp >= my) pq.push(tmp);}if(pq.empty()) {puts("0");return 0;}while(my<=pq.top()){my++;ans++;tmp = pq.top();pq.pop();pq.push(tmp-1);}printf("%d\n",ans);return 0; }

wa代碼：

#include<bits/stdc++.h>using namespace std; const int MAX = 1e5 +5; int a[MAX]; int main() {int n,my,top=0,tmp;cin>>n;scanf("%d",&my);for(int i = 2; i<=n; i++) {scanf("%d",&tmp);if(tmp >= my) a[++top] = tmp;}if(top == 0) {puts("0");return 0;}int sum = my;for(int i = 1; i<=top; i++) {sum += a[i];}double ans = ceil(sum*1.0/(top+1));if(sum%(top+1) == 0) {printf("%d\n",(int)ans-my + 1);}else printf("%d\n",(int)ans-my);return 0 ;}

總結：

? 剛開始想錯了，想直接找到平均值然后看是否需要加1就可以了。但是這樣是不對的，因為比如1,897,2這三個數，平均值是300，但是你答案不能直接在300附近找，因為這樣看的話相當于897也分給了2一部分，才能平均成300，但是依據題意，只有1號選手可以賄賂其他人，而對于其他人，得票數只能減少不能增加的！（也就是，其他人都不能賄賂別人）。所以這種策略（直接算平均值）是失效的，對于這個題。

emmm想一下，這題也可以二分答案去做嗎？

總結

以上是生活随笔為你收集整理的*【CodeForces - 574A】Bear and Elections （优先队列，水题模拟）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。