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 a_{i} 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 a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 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.

Difficulty: interview

Starter code:

Solutions:
n=int(input())
a=list(map(int,input().split()))
b=0
a[1:]=sorted(a[1:])
while a[0]<=a[-1]:
    a[-1]-=1
    a[0]+=1
    b+=1
    a[1:]=sorted(a[1:])
print(b)


#Brute

n = int(input())
a = [int(i) for i in input().split()]
p = a[0]
a = a[1:]
w = 0

while p <= max(a):
    p += 1
    q = max(a)
    a.remove(q)
    a.append(q-1)
    w += 1

print(w)

n = int(input())
a = list(map(int, input().split()))
q = a.pop(0)
a.sort()
sum = 0
while q <= a[-1]:
    a[-1] -= 1
    a.sort()
    q += 1
    sum += 1
print(sum)


    


n = int(input())
a = list(map(int, input().split()))
b = a[1:]
m = max(b)
ans = 0
mi = b.index(max(b))
while a[0] <= m:
    b[mi] -= 1
    ans += 1
    a[0] += 1
    m = max(b)
    mi = b.index(max(b))
print(ans)


#In the name of Allah

from sys import stdin, stdout
input = stdin.readline

n = int(input())
a = list(map(int, input().split()))
v = a[0]
a = sorted(a[1:], reverse = True)
ans = 0

if len(a) == 1:
         a += [0]

while v <= a[0]:
         v += 1
         ans += 1
         a[0] -= 1
         if a[0] < a[1]:
                  a.sort(reverse = True)
                  
stdout.write(str(ans))


def check(m, a):
    for i in range(1, len(a)):
        if a[i] >= m:
            return True
    return False

n = int(input())
a = list(map(int, input().split()))
ms = a[0]
ans = 0
while check(a[0], a):
    pos = a[1:].index(max(a)) + 1
    a[pos] -= 1
    a[0] += 1
    ans += 1
print(ans)


#!/usr/bin/env python
# 574A_bear.py - Codeforces.com 574A Bear program by Sergey 2015

import unittest
import sys

###############################################################################
# Bear Class
###############################################################################


class Bear:
    """ Bear representation """

    def __init__(self, test_inputs=None):
        """ Default constructor """

        it = iter(test_inputs.split("\n")) if test_inputs else None

        def uinput():
            return next(it) if it else sys.stdin.readline().rstrip()

        # Reading single elements
        self.n = int(uinput())

        # Reading a single line of multiple elements
        self.nums = list(map(int, uinput().split()))

    def calculate(self):
        """ Main calcualtion function of the class """

        lamak = self.nums[0]
        srt = sorted(self.nums[1:])
        result = 0

        while lamak <= srt[-1]:
            srt[-1] -= 1
            lamak += 1
            result += 1
            srt = sorted(srt)

        return str(result)

###############################################################################
# Unit Tests
###############################################################################


class unitTests(unittest.TestCase):

    def test_single_test(self):
        """ Bear class testing """

        # Constructor test
        test = "5\n5 1 11 2 8"
        d = Bear(test)
        self.assertEqual(d.n, 5)
        self.assertEqual(d.nums, [5, 1, 11, 2, 8])

        # Sample test
        self.assertEqual(Bear(test).calculate(), "4")

        # Sample test
        test = "4\n1 8 8 8"
        self.assertEqual(Bear(test).calculate(), "6")

        # Sample test
        test = "2\n7 6"
        self.assertEqual(Bear(test).calculate(), "0")

        # My tests
        test = "4\n0 1 1 1"
        self.assertEqual(Bear(test).calculate(), "2")

        # Time limit test
        self.time_limit_test(100)

    def time_limit_test(self, nmax):
        """ Timelimit testing """
        import random
        import timeit

        # Random inputs
        test = str(nmax) + "\n"
        test += "0 "
        nums = [1000 for i in range(nmax-1)]
        test += " ".join(map(str, nums)) + "\n"

        # Run the test
        start = timeit.default_timer()
        d = Bear(test)
        calc = timeit.default_timer()
        d.calculate()
        stop = timeit.default_timer()
        print(("\nTimelimit Test: " +
              "{0:.3f}s (init {1:.3f}s calc {2:.3f}s)".
              format(stop-start, calc-start, stop-calc)))

def __starting_point():

    # Avoiding recursion limitaions
    sys.setrecursionlimit(100000)

    if sys.argv[-1] == "-ut":
        unittest.main(argv=[" "])

    # Print the result string
    sys.stdout.write(Bear().calculate())

__starting_point()

import heapq

n = int(input())
votes = [-int(e) for e in input().split()]
limak = -votes[0]
votes = votes[1:]
heapq.heapify(votes)
ans = 0

while limak <= -votes[0]:
    cur = heapq.heappop(votes)
    cur += 1
    limak += 1
    ans += 1
    heapq.heappush(votes, cur)

print(ans)

from sys import stdin, stdout
input = stdin.readline

n = int(input())
a = list(map(int, input().split()))
l = a[0]
ans = 0
ops = a[1:]
ops = sorted(ops, reverse=True)
max_op = ops[0]

while l <= max_op:
  for i,el in enumerate(ops):
      if el == max_op:
        ops[i] -= 1
        ans += 1
        l += 1
        if l > max_op:
            break
  max_op = max(ops)

stdout.write(str(ans))

n = int(input())
arr = list(map(int, input().split()))
st = arr[0]
ind = arr.index(max(arr))
while (arr[0] < max(arr[1:])):
	arr[ind] -= 1
	arr[0] += 1
	ind = arr.index(max(arr))
if (arr[0] == max(arr[1:])):
	k = (arr[0] + 1)
else:
	k = (arr[0])
print(k - st)

n = int(input())
c = list(map(int, input().split()))
count = 0
while True:
    maxx = c[0]
    point = 0
    for i in range(len(c)):
        if c[i] >= maxx:
            maxx = c[i]
            point = i
    if point != 0:
        c[0] += 1
        c[point] -= 1
        count += 1
    else:
        break
print(count)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import time

n   = int(input())
A   = [int(i) for i in input().split()]

start = time.time()

l0  = A[0]
l   = A[0]
A   = A[1:]
m   = max(A)

while l <= m:
    l += 1
    A[A.index(m)] -= 1
    m = max(A)

print(l-l0)
finish = time.time()
#print(finish - start)


n = int(input())
arr = list(map(int, input().split()))
mishka = arr[0]
arr[0] = -1

ans = 0

while(mishka < max(arr) and mishka != max(arr)):
    mishka += 1
    arr[arr.index(max(arr))] = max(arr) - 1
    ans += 1

if(mishka == max(arr)):
    ans += 1

print(ans)

N = int(input())
votes = [int(x) for i, x in enumerate(input().split())]
my = votes[0]
old = my
votes = sorted(votes[1:], key=lambda x: -x)
while my <= votes[0]:
    votes[0] -= 1
    my += 1
    i = 0
    while i + 1 < len(votes) and votes[i] < votes[i + 1]:
        votes[i], votes[i + 1] = votes[i + 1], votes[i]
        i += 1
print(my - old)


import heapq
n=int(input())
a=list(map(int,input().split()))
b=a[0]
a=a[1:]
for i in range(n-1):
    a[i]=-a[i]
heapq.heapify(a)
ans=0
while(True):
    cur=heapq.heappop(a)
    cur=-cur
    if cur<b:
        break
    ans+=1
    b+=1
    cur-=1
    cur=-cur
    heapq.heappush(a,cur)
print(ans)


n = int(input())
a = list(map(int, input().split(" ")))
l = a[0]
c = a[1:]
result = 0
while(True):
    c.sort(reverse=True)
    if l > c[0]:
        break
    else:
        l += 1
        c[0] -= 1
        result+=1

print(result)
    


N = int(input())
x = [int(i) for i in input().split()]

import operator
iters = 0

while True:
    i, v = max(enumerate(x[1:]), key=operator.itemgetter(1))
    if x[0] > max(x[1:]):
        print(iters)
        break
    x[i + 1] -= 1
    x[0] += 1
    iters += 1


n = int(input())
a = list(map(int, input().split()))

cnt = 0
while max(a[1:]) >= a[0]:
    i = 0
    for j in range(len(a)):
        if a[j] == max(a):
            i = j
    a[i] -= 1
    a[0] += 1
    cnt += 1
print(cnt)


n = int(input())
cand = [int(i) for i in input().split()]
opp = cand[1:]
opp.sort()
lemak = cand[0]
result = 0
while lemak <= opp[-1]:
    lemak +=1 
    opp[-1] -= 1
    result += 1
    opp.sort()
print(result)

n = int(input())
a = list(map(int, input().split()))

limak = a[0]
a = a[1:]

c = [0] * (1001)
for votes in a:
    c[votes] += 1

ans = 0
cur_max = max(a)
while limak <= cur_max:
    limak += 1
    ans += 1
    c[cur_max] -= 1
    c[cur_max - 1] += 1
    if c[cur_max] == 0:
        cur_max -= 1
    
print(ans)

x = int(input(''))

rida = input('')

rida = rida.split()
nrs = list(map(int, rida))

count = nrs.pop(0)
startcount = count

while count <= max(nrs):
    ind = nrs.index(max(nrs))
    nrs[ind] = nrs[ind] - 1
    count = count + 1


print(str(count - startcount))
    




#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# AUTHOR: haya14busa
import sys
import io

from collections import Counter

def solve(n, vs):
    # vs: votes
    assert 2 <= n <= 1000
    # Limak's vote is vs[0]
    for v in vs:
        assert 1 <= v <= 1000

    # limak's vote, rest's votes
    lv, rvs = vs[0], vs[1:]
    cnt = 0

    votes = Counter(rvs)
    max_vote = max(rvs)

    while lv <= max_vote:
        votes[max_vote] -= 1
        votes[max_vote - 1] += 1
        if votes[max_vote] == 0:
            max_vote -= 1
        lv += 1
        cnt += 1

    return cnt


def getinput():
    def getint():
        return int(input())

    def getints_line():
        return list(map(int, input().split(' ')))

    def getints(n):
        return [getint() for _ in range(n)]

    def getints_lines(n):
        return [getints_line() for _ in range(n)]
    return [getint(), getints_line()]


def iosolve():
    return str(solve(*getinput()))
    # return 'YES' if solve(*getinput()) else 'NO' # for boolean output
    # return '\n'.join(map(str, solve(*getinput()))) # for multiple line output


def main():
    if sys.stdin.isatty():
        test()
    stdin_lines = getstdin_lines()
    sys.stdin = io.StringIO('\n'.join(stdin_lines))
    if stdin_lines:
        print(iosolve())
    else:
        test()


def test():
    IO_TEST_CASES = [

        (
            # INPUT
            '''\
5
5 1 11 2 8
            ''',
            # EXPECT
            '''\
4
            '''
        ),

        (
            # INPUT
            '''\
4
1 8 8 8
            ''',
            # EXPECT
            '''\
6
            '''
        ),

        (
            # INPUT
            '''\
2
7 6
            ''',
            # EXPECT
            '''\
0
            '''
        ),

    ]

    # List[(List[arg for solve()], expect)]
    TEST_CASES = [
        # ([], None),
    ]

    # You do need to see below
    import unittest  # to save memory, import only if test required
    import sys
    import io

    class Assert(unittest.TestCase):
        def equal(self, a, b):
            self.assertEqual(a, b)

        def float_equal(self, actual, expect, tolerance):
            self.assertTrue(expect - tolerance < actual < expect + tolerance)

    art = Assert()

    for inputs, expect in TEST_CASES:
        art.equal(solve(*inputs), expect)

    for stdin, expect in IO_TEST_CASES:
        sys.stdin = io.StringIO(stdin.strip())
        art.equal(iosolve(), expect.strip())
        # art.float_equal(float(iosolve()), float(expect.strip()), 10 ** -6)


def getstdin_lines():
    stdin = []
    while 1:
        try:
            stdin.append(input())
        except EOFError:
            break
    return stdin

def __starting_point():
    main()

__starting_point()

def check(n, lst, lk):
    lst[0] += lk
    for i in range(1, n):
        if lst[i] >= lst[0]:
            lk -= lst[i] - lst[0] + 1
    if lk >= 0:
        return True
    return False
n = int(input())
lst = list(map(int, input().split()))
left = -1
right = 100000
while left + 1 < right:
    middle = (left + right) // 2
    if check(n, lst.copy(), middle):
        right = middle
    else:
        left = middle
print(right)
            


n = int(input())
a = list(map(int, input().split()))
i = -1
k = 0
lim = a[0]
a[0] = 0
a = sorted(a)
n -= 1
while lim <= a[-1]:
    while lim <= a[-1] and a[-1] >= a[-2]:
        lim += 1
        a[-1] -= 1
        k += 1
    while i > -n and a[i] < a[i - 1]:
        a[i], a[i - 1], i = a[i - 1], a[i], i - 1
    i = -1
print(k)

s = input()
l, *v = (int(x) for x in input().split())
v.sort(reverse=True)
count = 0
while l <= v[0]:
	if len(v) == 1 or v[0] > v[1]:
		count += 1
		l += 1
		v[0] -= 1
	else:
		count += 1
		l += 1
		v[0] -= 1
		v.sort(reverse=True)
print(count)