One day n friends gathered together to play "Mafia". During each round of the game some player must be the supervisor and other n - 1 people take part in the game. For each person we know in how many rounds he wants to be a player, not the supervisor: the i-th person wants to play ai rounds. What is the minimum number of rounds of the "Mafia" game they need to play to let each person play at least as many rounds as they want?

Input

The first line contains integer n (3 ≤ n ≤ 105). The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the i-th number in the list is the number of rounds the i-th person wants to play.

Output

In a single line print a single integer — the minimum number of game rounds the friends need to let the i-th person play at least ai rounds.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

3
3 2 2


Output

4


Input

4
2 2 2 2


Output

3

Note

You don't need to know the rules of "Mafia" to solve this problem. If you're curious, it's a game Russia got from the Soviet times: http://en.wikipedia.org/wiki/Mafia_(party_game).
3
1000000000 1000000000 10000000
 3
1 2 1
 3
4 10 11
 5
1000000000 5 5 4 4
 5
1000000000 1000000000 1000000000 1000000000 1000000000
 10
94 96 91 95 99 94 96 92 95 99
 7
9 7 7 8 8 7 8
 3
1 1 1
 3
677876423 834056477 553175531
 10
13 12 10 13 13 14 10 10 12 12
 5
1000000000 1 1 1 1
 100
1 555 876 444 262 234 231 598 416 261 206 165 181 988 469 123 602 592 533 97 864 716 831 156 962 341 207 377 892 51 866 96 757 317 832 476 549 472 770 1000 887 145 956 515 992 653 972 677 973 527 984 559 280 346 580 30 372 547 209 929 492 520 446 726 47 170 699 560 814 206 688 955 308 287 26 102 77 430 262 71 415 586 532 562 419 615 732 658 108 315 268 574 86 12 23 429 640 995 342 305
 4
1 2 3 4
 3
2 1 1
 4
1000000000 1000000000 1000000000 1000000000
 30
94 93 90 94 90 91 93 91 93 94 93 90 100 94 97 94 94 95 94 96 94 98 97 95 97 91 91 95 98 96

1005000000
 2
 13
 1000000000
 1250000000
 106
 9
 2
 1032554216
 14
 1000000000
 1000
 4
 2
 1333333334
 100

#!/usr/bin/env python
from __future__ import division, print_function
import math
import os
import sys
from fractions import *
from sys import *
from io import BytesIO, IOBase
from itertools import *
from collections import *

# sys.setrecursionlimit(10**5)
M = 10 ** 9 + 7

# print(math.factorial(5))
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
# sys.setrecursionlimit(10**6)

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def fsep(): return map(float, inp().split())


def inpu(): return int(inp())


# -----------------------------------------------------------------

def regularbracket(t):
    p = 0
    for i in t:
        if i == "(":
            p += 1
        else:
            p -= 1
        if p < 0:
            return False
    else:
        if p > 0:
            return False
        else:
            return True


# -------------------------------------------------
def binarySearchCount(arr, n, key):
    left = 0
    right = n - 1

    count = 0

    while (left <= right):
        mid = int((right + left) / 2)

        # Check if middle element is
        # less than or equal to key
        if (arr[mid] <= key):
            count = mid + 1
            left = mid + 1
        # If key is smaller, ignore right half
        else:
            right = mid - 1
    return count


# ------------------------------reverse string(pallindrome)
def reverse1(string):
    pp = ""
    for i in string[::-1]:
        pp += i
    if pp == string:
        return True
    return False


# --------------------------------reverse list(paindrome)
def reverse2(list1):
    l = []
    for i in list1[::-1]:
        l.append(i)
    if l == list1:
        return True
    return False


def mex(list1):
    # list1 = sorted(list1)
    p = max(list1) + 1
    for i in range(len(list1)):
        if list1[i] != i:
            p = i
            break
    return p


def sumofdigits(n):
    n = str(n)
    s1 = 0
    for i in n:
        s1 += int(i)
    return s1


def perfect_square(n):
    s = math.sqrt(n)
    if s == int(s):
        return True
    return False


# -----------------------------roman
def roman_number(x):
    if x > 15999:
        return
    value = [5000, 4000, 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbol = ["F", "MF", "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    roman = ""
    i = 0
    while x > 0:
        div = x // value[i]
        x = x % value[i]
        while div:
            roman += symbol[i]
            div -= 1
        i += 1
    return roman


def soretd(s):
    for i in range(1, len(s)):
        if s[i - 1] > s[i]:
            return False
    return True


# print(soretd("1"))
# ---------------------------
def countRhombi(h, w):
    ct = 0
    for i in range(2, h + 1, 2):
        for j in range(2, w + 1, 2):
            ct += (h - i + 1) * (w - j + 1)
    return ct


def countrhombi2(h, w):
    return ((h * h) // 4) * ((w * w) // 4)


# ---------------------------------
def binpow(a, b):
    if b == 0:
        return 1
    else:
        res = binpow(a, b // 2)
    if b % 2 != 0:
        return res * res * a
    else:
        return res * res


# -------------------------------------------------------
def binpowmodulus(a, b, m):
    a %= m
    res = 1
    while (b > 0):
        if (b & 1):
            res = res * a % m
        a = a * a % m
        b >>= 1
    return res


# -------------------------------------------------------------
def coprime_to_n(n):
    result = n
    i = 2
    while (i * i <= n):
        if (n % i == 0):
            while (n % i == 0):
                n //= i
            result -= result // i
        i += 1
    if (n > 1):
        result -= result // n
    return result


# -------------------prime
def prime(x):
    if x == 1:
        return False
    else:
        for i in range(2, int(math.sqrt(x)) + 1):
            # print(x)
            if (x % i == 0):
                return False
        else:
            return True


def luckynumwithequalnumberoffourandseven(x, n, a):
    if x >= n and str(x).count("4") == str(x).count("7"):
        a.append(x)
    else:
        if x < 1e12:
            luckynumwithequalnumberoffourandseven(x * 10 + 4, n, a)
            luckynumwithequalnumberoffourandseven(x * 10 + 7, n, a)
    return a


def luckynuber(x, n, a):
    p = set(str(x))
    if len(p) <= 2:
        a.append(x)
    if x < n:
        luckynuber(x + 1, n, a)
    return a


# ------------------------------------------------------interactive problems

def interact(type, x):
    if type == "r":
        inp = input()
        return inp.strip()
    else:
        print(x, flush=True)


# ------------------------------------------------------------------zero at end of factorial of a number
def findTrailingZeros(n):
    # Initialize result
    count = 0

    # Keep dividing n by
    # 5 & update Count
    while (n >= 5):
        n //= 5
        count += n

    return count


# -----------------------------------------------merge sort
# Python program for implementation of MergeSort
def mergeSort(arr):
    if len(arr) > 1:

        # Finding the mid of the array
        mid = len(arr) // 2

        # Dividing the array elements
        L = arr[:mid]

        # into 2 halves
        R = arr[mid:]

        # Sorting the first half
        mergeSort(L)

        # Sorting the second half
        mergeSort(R)

        i = j = k = 0

        # Copy data to temp arrays L[] and R[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1


# -----------------------------------------------lucky number with two lucky any digits
res = set()


def solven(p, l, a, b, n):  # given number
    if p > n or l > 10:
        return
    if p > 0:
        res.add(p)
    solven(p * 10 + a, l + 1, a, b, n)
    solven(p * 10 + b, l + 1, a, b, n)


# problem
"""
n = int(input())
for a in range(0, 10):
    for b in range(0, a):
        solve(0, 0)
print(len(res))
"""


# Python3 program to find all subsets
# by backtracking.

# In the array A at every step we have two
# choices for each element either we can
# ignore the element or we can include the
# element in our subset
def subsetsUtil(A, subset, index, d):
    print(*subset)
    s = sum(subset)
    d.append(s)
    for i in range(index, len(A)):
        # include the A[i] in subset.
        subset.append(A[i])

        # move onto the next element.
        subsetsUtil(A, subset, i + 1, d)

        # exclude the A[i] from subset and
        # triggers backtracking.
        subset.pop(-1)
    return d


def subsetSums(arr, l, r, d, sum=0):
    if l > r:
        d.append(sum)
        return
    subsetSums(arr, l + 1, r, d, sum + arr[l])

    # Subset excluding arr[l]
    subsetSums(arr, l + 1, r, d, sum)
    return d


def print_factors(x):
    factors = []
    for i in range(1, x + 1):
        if x % i == 0:
            factors.append(i)
    return (factors)


# -----------------------------------------------
def calc(X, d, ans, D):
    # print(X,d)
    if len(X) == 0:
        return

    i = X.index(max(X))
    ans[D[max(X)]] = d

    Y = X[:i]
    Z = X[i + 1:]

    calc(Y, d + 1, ans, D)
    calc(Z, d + 1, ans, D)


# endregion------------------------------
"""
def main():
    t = inpu()
    for _ in range(t):
        a,b,c = sep()
        l=[a,b,c]
        l.sort()
        if sum(l)%9==0 and l[0]>=sum(l)//9:
            print("YES")
        else:
            print("NO")
if __name__ == '__main__':
    main()

46417578 46590175 7599314
"""
"""
def main():
    t = inpu()
    for _ in range(t):
        s = inp()
        p=0
        cnt=len(s)
        q=0
        for i in range(cnt):
            if s[i] =="+":
                p+=1
            else:
                q+=1
            if q>p:
                cnt+=(i+1)
                q-=1
        print(cnt)
if __name__ == '__main__':
    main()
"""
"""
def main():
    t=inpu()
    for _ in range(t):
        n=inpu()
        i=1
        cnt=0
        i=1
        while(True):
            b = ((i*i)-1)/2
            if b>=n:
                break
            if b==int(b) and b>=1 and 1+b<=n:
                cnt+=1
            i+=2
        print(cnt)
if __name__ == '__main__':
    main()
"""
"""
def main():
    n = inpu()
    x=1
    while int(bin(x).replace("0b","")) <= n:
        x += 1
    print(x-1)
if __name__ == '__main__':
    main()
"""
"""
def main():
    a = [i for i, j in enumerate(input(), 1) if j == '1']
    m = int(input())
    q = [(-1, 0, 0, [])]
    p = 'NO'
    while q:
        x, y, z, t = q.pop()
        if z == m:
            p = 'YES\n' + ' '.join(map(str, t))
            break
        for i in a:
            if i != x and i > y:
                q.append((i, i - y, z + 1, t + [i]))
    print(p)
if __name__ == '__main__':
    main()
"""
"""
def main():
    t=inpu()
    for _ in range(t):
        n=inpu()
        arr=lis()
        i = k = 0
        while k < len(arr):
                k += 1
                j = arr.index(k)
                if j >= i:
                    arr.insert(i, arr.pop(j))
                    if i==j:
                        i=i+1
                    else:
                        i=j
        print(*arr)
if __name__ == '__main__':
    main()
"""
"""
def main():
    for _ in range(inpu()):
        n, m = sep()
        l = []
        sum = 0
        for i in range(n):
            l.append(list(sep()))
        for i in range(n):
            for j in range(m):
                a = list(sorted([l[i][j], l[n - i - 1][j], l[i][m - j - 1], l[n - i - 1][m - j - 1]]))
                #print(a)
                sum += (a[3] + a[2] - a[1] - a[0])
                #print(sum)
        print(sum // 4)
        print(l)
if __name__ == '__main__':
    main()
"""


def good(b):
    l = []
    i = 0
    while (len(b) != 0):
        if b[i] < b[len(b) - 1 - i]:
            l.append(b[i])
            b.remove(b[i])
        else:
            l.append(b[len(b) - 1 - i])
            b.remove(b[len(b) - 1 - i])
    if l == sorted(l):
        # print(l)
        return True
    return False


# arr=[]
# print(good(arr))
def generate(st, s):
    if len(s) == 0:
        return

    # If current string is not already present.
    if s not in st:
        st.add(s)

        # Traverse current string, one by one
        # remove every character and recur.
        for i in range(len(s)):
            t = list(s).copy()
            t.remove(s[i])
            t = ''.join(t)
            generate(st, t)
    return


"""
def main():
    n = inp()
    st = set()
    generate(st,n)
    l=[]
    print(st)
    for i in st:
        i = list(i)
        for j in (i):
            if j == "0":
                i.remove(j)
            else:
                break
        ans = ""
        for pp in i:
            ans += pp
        print(ans + "---------------")
        if len(ans)>0:
            if prime(int(ans))==True and reverse1(ans)==True:
                print(ans)
                l.append(int(ans))
    l = set(l)
    l=list(l)
    print(l)
    i=0
    while(i<len(l)):
        if l[i]==0:
            l.remove(l[i])
        else:
            i+=1
    if len(l)==0:
        print(-1)
    else:
        l.sort()
        for i in l:
            print(i,end=" ")
if __name__ == '__main__':
    main()
"""
"""
def main():
    t = int(input())
    for _ in range(t):
            a, b = sep()
            s=list(inp())
            flag = 1

            for i in range(len(s)):
                if s[i] == "0":
                    if s[len(s) - 1 - i] == "1":
                        flag = 0
                        break
                    else:
                        s[len(s) - 1 - i] = "0"
                elif s[i] == "1":
                    if s[len(s) - 1 - i] == "0":
                        flag = 0
                        break
                    else:
                        s[len(s) - 1 - i] = "1"

            if flag == 0:
                print(-1)
                continue

            for ss in s:
                if ss == "0":
                    a -= 1
                elif ss == "1":
                    b -= 1

            if a < 0 or b < 0:
                print(-1)
                continue

            if s[len(s) // 2] == "?":
                if a % 2 == 1:
                    s[len(s) // 2] = "0"
                    a -= 1
                elif b % 2 == 1:
                    s[len(s) // 2] = "1"
                    b -= 1

            if a % 2 == 1 or b % 2 == 1:
                print(-1)
                continue

            for i in range(len(s)):
                if s[i] == "?":
                    if a > 0:
                        s[i] = "0"
                        s[len(s) - 1 - i] = "0"
                        a -= 2
                    else:
                        s[i] = "1"
                        s[len(s)- 1 - i] = "1"

            print("".join(s))
if __name__ == '__main__':
    main()
"""
"""
def main():
    t = inpu()
    for _ in range(t):
        n = inpu()
        l=[]
        for i in range(n):
            arr = list(input())
            l.append(arr)
        ans=[]
        for i in range(n):
            for j in range(n):
                if l[i][j]=="*":
                    ans.append([i,j])
        #print(ans)
        if ans[0][0]==ans[1][0]:
            if ans[0][0]==0:
                #print(6)
                l[1][ans[0][1]]="*"
                l[1][ans[1][1]]="*"
            else:
                l[0][ans[0][1]] = "*"
                l[0][ans[1][1]] = "*"
        elif ans[0][1]==ans[1][1]:
            if ans[0][1]==0:
                l[ans[0][0]][1]="*"
                l[ans[1][0]][1]="*"
            else:
                l[ans[0][0]][0] = "*"
                l[ans[1][0]][0] = "*"
        else:
            l[ans[0][0]][ans[1][1]]="*"
            l[ans[1][0]][ans[0][1]]="*"
        #print(l)
        for i in range(n):
            for j in range(n):
                print(l[i][j],end="")
            print()
if __name__ == '__main__':
    main()
"""
"""
def main():
    t=inpu()
    for _ in range(t):
        n=inpu()
        arr=lis()
        arr.sort()
        n+=2
        s1 = sum(arr[:n-2])
        if s1==arr[n-2]:
            print(*arr[:n-2])
        elif s1==arr[n-1]:
            print(*arr[:n-2])
        else:
            for i in range(len(arr)-2):
                c=s1
                c-=arr[i]
                d=c
                c+=arr[n-2]
                if c==arr[n-1]:
                    arr.remove(arr[i])
                    arr.remove(arr[len(arr)-1])
                    print(*arr)
                    break
            else:
                print(-1)
if __name__ == '__main__':
    main()
"""
"""
def main():
    t=inpu()
    for _ in range(t):
        n = inpu()
        a = lis()
        mod = 1000000007
        x = a[0]
        for i in range(1, n):
            x &= a[i]
        #print(x)
        cnt = a.count(x)
        if cnt < 2:
            print(0)
        else:
            first = (cnt * (cnt - 1))
            second = math.factorial(n - 2)
            print((first * second) % mod)
if __name__ == '__main__':
    main()
"""
"""
def main():
    t = inpu()
    for _ in range(t):
        n=inpu()
        arr=lis()
        l=[]
        ans=[]
        if arr[0]!=min(arr):
            ans.append(min(arr))
        else:
            ans.append(arr[1])
        for i in range(1,n):
            l.append(arr[i]+arr[i-1])
        #print(l)
        for i in range(n-1):
            ans.append(l[i]-ans[i])
        print(*ans)
if __name__ == '__main__':
    main()
"""

"""
def main():
    t = int(input())
    for tests in range(t):
        n, l, r, s = map(int, input().split())

        x = r - l + 1

        if x * (x + 1) // 2 <= s <= (n + n - x + 1) * x // 2:
            True
        else:
            print(-1)
            continue

        ANS = list(range(1, x + 1))
        ANS.reverse()
        SUM = x * (x + 1) // 2
        rest = s - SUM
        MAX = n

        i = 0
        while rest:
            k = min(MAX, ANS[i] + rest)
            rest -= k - ANS[i]
            ANS[i] = k
            i += 1
            MAX -= 1

        # print(ANS)

        ANS2 = [-1] * n
        USE = [0] * (n + 3)
        USE[0] = 1

        j = 0

        for i in range(l - 1, r):
            ANS2[i] = ANS[j]
            j += 1
            USE[ANS2[i]] = 1

        j = 0

        for i in range(n):
            while USE[j] == 1:
                j += 1
            if ANS2[i] == -1:
                ANS2[i] = j
                j += 1
        print(*ANS2)
if __name__ == '__main__':
    main()
"""
"""
def main():
    mxn = 2 * (10 ** 5) + 10
    mod = 10 ** 9 + 7
    dp = [1] * mxn
    for i in range(10, mxn):
        dp[i] = (dp[i - 9] + dp[i - 10]) % mod
    for test in range(int(input())):
        n, k = sep()
        ans = 0
        while n:
            ans = (ans + dp[k + n % 10]) % mod
            n //= 10
        print(ans)
if __name__ == '__main__':
    main()
"""
"""
def main():
    t = inpu()
    for _ in range(t):
        n=inpu()
        arr = lis()
        alice=0
        bob=0
        q=0
        moves=0
        while(True):
            #print(arr,q,bob)
            s=0
            j=0
            c=0
            while(j<len(arr)):
                s+=arr[j]
                j+=1
                c+=1
                if s>q:
                    for i in range(c):
                        alice+=arr[0]
                        arr.pop(0)
                    moves+=1
                    q=s
                    break
            else:
                #print(arr)
                if len(arr)!=0:
                    moves+=1
                alice+=sum(arr)
                break

            t=0
            j=0
            c=0
            #print(arr,q,bob)
            while(j<len(arr)):
                t+=arr[::-1][j]
                j+=1
                c+=1
                if t>q:
                    for i in range(c):
                        bob+=arr[-1]
                        arr.pop(-1)
                    q=t
                    moves+=1
                    break
            else:
                if len(arr)!=0:
                    moves+=1
                #print(arr)
                bob+=sum(arr)
                break
            #moves+=1
        print(moves,alice,bob)
if __name__ =='__main__':
    main()
"""
def main():
    n = inpu()
    arr = lis()
    print(max(max(arr), (sum(arr) + (n - 2)) // (n - 1)))
if __name__ == '__main__':
    main()
