Problem:


Score: 400 points

Problem Statement

Quickly after finishing the tutorial of the online game ATChat, you have decided to visit a particular place with N-1 players who happen to be there. These N players, including you, are numbered 1 through N, and the friendliness of Player i is A_i.

The N players will arrive at the place one by one in some order. To make sure nobody gets lost, you have set the following rule: players who have already arrived there should form a circle, and a player who has just arrived there should cut into the circle somewhere.

When each player, except the first one to arrive, arrives at the place, the player gets comfort equal to the smaller of the friendliness of the clockwise adjacent player and that of the counter-clockwise adjacent player. The first player to arrive there gets the comfort of 0.

What is the maximum total comfort the N players can get by optimally choosing the order of arrivals and the positions in the circle to cut into?

Constraints

All values in input are integers.

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the maximum total comfort the N players can get.

Sample Input 1

4
2 2 1 3

Sample Output 1

7

By arriving at the place in the order Player 4, 2, 1, 3, and cutting into the circle as shown in the figure, they can get the total comfort of 7.

They cannot get the total comfort greater than 7, so the answer is 7.

Sample Input 2

7
1 1 1 1 1 1 1

Sample Output 2

6



Sample input:
4
2 2 1 3


Sample output:
7

Submission status: Runtime Error

Solution code:
"""import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
# region fastio
 
BUFSIZE = 8192
 
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")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort(reverse = True)
    b = []
    c = []
    for i in range(n):
        if i%2 == 0:
            b.append(a[i])
        else:
            c.append(a[i])
    print(sum(b), sum(c))

if __name__ == "__main__":
    main()"""
    
#===============================================================================================
#importing some useful libraries.
from fractions import Fraction
import sys
import bisect
import heapq
from math import *
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned
import statistics 
from statistics import mode
from functools import reduce
#===============================================================================================
#some shortcuts
 
mod = 1000000007
def inp(): return sys.stdin.readline().strip() #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 graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def most_frequent(List): 
    occurence_count = Counter(List) 
    return occurence_count.most_common(1)[0][0]
def most_common(List): 
    return(mode(List))
def chinese_remainder(a, p):
    """returns x s.t. x = a[i] (mod p[i]) where p[i] is prime for all i"""
    prod = reduce(op.mul, p, 1)
    x = [prod // pi for pi in p]
    return sum(a[i] * pow(x[i], p[i] - 2, p[i]) * x[i] for i in range(len(a))) % prod
def createMatrix(rowCount, colCount, dataList):   
    mat = []
    for i in range (rowCount):
        rowList = []
        for j in range (colCount):
            if dataList[j] not in mat:
                rowList.append(dataList[j])
        mat.append(rowList)

    return mat
def isprime(n) : 
  
    if (n <= 1) :
        return False
    if (n <= 3) :
        return True
  
    
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
  
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
  
    return True
    

import collections
"""def getFolderNames(names):
        exists = set()
        last = collections.defaultdict(int)
        result = []
        for name in names:
            k = last[name]
            modified = name
            while modified in exists:
                k += 1
                modified = f'{name}({k})'
            last[name] = k
            result.append(modified)
            exists.add(modified)
        return result

names = input()
#names = list(names)
print(getFolderNames(names))"""


"""n1, n2 = map(int, inp().split())
a = []
e = 0
g = 0
j = 0
k = []
#if(n1 == 2):
    #a.append(n1)
for i in range(n1, n2+1):
    if(isprime(i) == True):
        a.append(i)
#print(a)
#print(len(a))
b = []
s = ''
for i in range(len(a)):
    for j in range(len(a)):
        if(a[i] != a[j]):
            s = str(a[i])+str(a[j])
            b.append(int(s))
            s = ''
b = set(b)
b = list(b)
c = []
#print(b)
#print(len(b))
for i in range(len(b)):
    if(isprime(b[i]) == True):
        c.append(b[i])
#print(c)
#print(len(c))
c.sort()
e = c[0]
g = c[-1]
h = len(c)
print(e,g)
for i in range(2,h):
    j = e+g
    e = g
    g = j
    k.append(j)
#if(j > 10**15):
 #   j = j%(2**64-1)
print(k)"""


"""for i in range(int(input())):
    n = int(input())
    a = 0
    while(n > 0):
        n = n//2
        a += 1
    print(a)"""

def minimalFilps1(bits): 
	n = len(bits) 

	# two arrays will keep the count for number 
	# of 0s' and 1s' to be flipped while 
	# traversing from left to right and right to 
	# left respectively 
	flipsFromLeft = [0 for i in range(n)] 
	flipsFromRight = [0 for i in range(n)] 

	# Fill flipsFromLeft[] 
	flips = 0
	for i in range(0, n, 1): 
		if (bits[i] == '1'): 
			flips = flips + 1	
		flipsFromLeft[i] = flips
	#print(flipsFromLeft)
	
	# Fill flipsFromRight[] 
	flips = 0
	i = n - 1
	while(i >= 0): 
		if (bits[i] == '0'): 
			flips = flips + 1
		i = i - 1
		flipsFromRight[i] = flips
	#print(flipsFromRight)
	
	# initialize minFlip to highest int value. 
	# If sum of leftflip and rightFlip is smaller 
	# than minflips, then update minFlips 
	minFlips1 = sys.maxsize 
	for i in range(1, n, 1): 
		if (flipsFromLeft[i - 1] +
			flipsFromRight[i] < minFlips1): 
			minFlips1 = (flipsFromLeft[i - 1] +
						flipsFromRight[i]) 
	
	return minFlips1 



def minimalFilps(bits): 
	n = len(bits) 

	# two arrays will keep the count for number 
	# of 0s' and 1s' to be flipped while 
	# traversing from left to right and right to 
	# left respectively 
	flipsFromLeft = [0 for i in range(n)] 
	flipsFromRight = [0 for i in range(n)] 

	# Fill flipsFromLeft[] 
	flips = 0
	for i in range(0, n, 1): 
		if (bits[i] == '0'): 
			flips = flips + 1	
		flipsFromLeft[i] = flips
	#print(flipsFromLeft)
	
	# Fill flipsFromRight[] 
	flips = 0
	i = n - 1
	while(i >= 0): 
		if (bits[i] == '1'): 
			flips = flips + 1
		i = i - 1
		flipsFromRight[i] = flips
	#print(flipsFromRight)
	
	# initialize minFlip to highest int value. 
	# If sum of leftflip and rightFlip is smaller 
	# than minflips, then update minFlips 
	minFlips = sys.maxsize 
	for i in range(1, n, 1): 
		if (flipsFromLeft[i - 1] +
			flipsFromRight[i] < minFlips): 
			minFlips = (flipsFromLeft[i - 1] +
						flipsFromRight[i]) 
	
	return minFlips 
def oddn(n):
    for i in range(2, n+1):
        if(i%2 != 0 and n%i == 0):
            return i
    return 3

#def memoize(fn):
#stored_results = {}

def memoized(*args):
    if args in stored_results:
        # try to get the cached result
        return stored_results[args]
    else:
        # nothing was cached for those args. let's fix that.
        result = stored_results[args] = fn(*args)
        return result
    return memoized

open_list = ["("]
close_list = [")"]
def check(myStr): 
    stack = []
    e = 0
    for i in myStr: 
        if i in open_list: 
            stack.append(i) 
        elif i in close_list: 
            pos = close_list.index(i) 
            if ((len(stack) > 0)): #and
                #(open_list[pos] == stack[len(stack)-1])): 
                stack.pop()
                e += 1
            #else: 
             #   return -1
    #if len(stack) == 0: 
     #   return 0
    #else: 
     #   return -1
    return e


"""n = int(input())
a = list(map(int, input().split()))
b = a.copy()
for i in range(n):
    if(a[i] == i+1):
        pass
    else:
        b[a[i]-1] = i+1
print(*b)"""

"""n = int(input())
a = list(map(int, input().split()))
b = []
c = []
#print(a)
i = 0
while(i < n):
    if i%2 == 0:
        if(a[0] > a[-1]):
            b.append(a[0])
            a.remove(a[0])
        else:
            b.append(a[-1])
            a.remove(a[-1])
    else:
        if(a[0] > a[-1]):
            c.append(a[0])
            a.remove(a[0])
        else:
            c.append(a[-1])
            a.remove(a[-1])
    i = i+1
#print(b)
#print(c)
print(sum(b), sum(c))"""

"""for i in range(int(input())):
    s = input()
    a = list(s)
    b = set(a)
    b = list(b)
    i = 0
    while(i < len(a)-1):
        if a[i] == a[i+1]:
            #print(a[i],i)
            a.pop(i)
            if len(a) > 0:
                a.pop(i)
                i = i-1
            else:
                a.clear()
            
        #print(a)
        i += 1
    
    a = set(a)
    a = list(a)
    a.sort()
    #b.sort()
    #if(len(a) > len(b)):
     #   print(*b,sep='')
    #else:
    print(*a,sep='')"""

"""n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
e = 0
g = [0]*n
v = []
for i in range(n):
    g[i] = a[i]+e
    e += a[i]
#print(g)

k = 0
i = 0
h = 0
j = 0
#for j in range(m):
while(j < m):
    #print(j)
    if b[j] <= g[i]:
        k = b[j]-h
        v.append((i+1,k))
    else:
        h = g[i]
        i += 1
        j = j-1
    j += 1
    #print(j)
    
for i in range(len(v)):
    print(*v[i],sep=' ')"""

"""n = int(input())
a = list(map(int, input().split()))
b = max(a)
a.remove(b)
for i in range(len(a)):
    a[i] = b-a[i]
if(len(a) == 0):
    c = 0
c = sum(a)
print(c)"""

"""def rev(o):
    if(o == 16 or o == 17 or o == 18 or o == 19 or 9-o>=0):
        if(o >= 6 and o < 10):
            p = (10-o)*60+1
        elif(o >= 16 and o < 20):
            p = (20-o)*60+2
        else:
            p = 10*o
    else:
        p = 0
        while(o>0):
            r = o%10
            o = o//10
            p = p*10+r
    return p
        
    
s = input()
a = list(s)
for i in a:
    if i == ':':
        a.remove(i)
b = a[:2]
c = a[2:]
#print(b,c)
e = c[::-1]
g = b[::-1]
k = 0
#print(b,e)
if(b == e):
    k = 0
else:
    h = ''.join(map(str,c))
    g = ''.join(map(str,g))
    o = ''.join(map(str,b))
    o = int(o)
    h = int(h)
    g = int(g)
    if(g == 60 or g == 70 or g == 80 or g == 90 or g == 61 or g == 71 or g == 81 or g == 91):
        k = -1
    else:
        k = g-h
    if k < 0:
        l = 60-h
        if o == 23:
            o = 0
        else:
            o += 1
            o = rev(o)
            
        k = o+l
print(k)"""

"""n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = {}
d = {}
for i in range(n):
    if a[i] in c:
        c[a[i]] += 1
    else:
        c[a[i]] = 1
for i in range(n):
    if b[i] in d:
        d[b[i]] += 1
    else:
        d[b[i]] = 1
print(c)
print(d)
e = 0
g = 0
h = 0
m = 0
o = 0
for i in c:
    if i in d:
        #e.append(i)
        if c[i] == d[i]:
            continue
        else:
            #m += 1
            if c[i] > d[i]:
                g = abs(c[i] - d[i])
            else:
                g = 0
            if(g%2 == 0):
                h += g//2
            else:
                h = -1
                break
    else:
        g = c[i]
        if(g%2 == 0):
            e += g//2
        else:
            e = -1
            break
for i in d:
    if i not in c:
        g = d[i]
        if(g%2 == 0):
            o += g//2
        else:
            o = -1
            
print(h,e,m,o)
if(h == -1 or e == -1 or o == -1):
    e = -1
else:
    #if(h > 0 and m > 0):
     #   h = h//m
    #if e+h > o:
     #   e = h+e-o
    #else:
    e = h+e
print(e)"""

"""s = input()
a = list(s)
for i in range(len(a)):
    a[i] = 26-(ord('z')-ord(a[i]))
    #print(a[i])
print(a)
b = 0
c = []
d = 0
e = 26-(ord('z')-ord('a'))
for i in range(len(a)):
    if(abs(a[i]-e) > 13):
        b += 26-abs(a[i]-e)
      #  c.append(b)
       # e = b-1
    else:
        b += abs(a[i]-e)
      #  c.append(b+1)
       # e = b
    #b += min(abs(1-a[i]),e-abs(1-a[i]))
    #e = a[i]
    #print(b)
    e = a[i]
print(b)
#print(max(c))"""


"""a1, a2, a3, a4 = map(int, input().split())
s = input()
b1, b2, b3, b4 = '1', '2', '3', '4'
b = 0
for i in s:
    if i == b1:
        b += a1
    elif i == b2:
        b += a2
    elif i == b3:
        b += a3
    else:
        b += a4
print(b)"""

"""a = input()
b = input()
a = list(a)
b = list(b)
c = 0
d = 0
e = 0
for i in range(len(a)):
    if(a[i].isupper()):
        a[i] = a[i].lower()
    if(b[i].isupper()):
        b[i] = b[i].lower()
for i in range(len(a)):
    if(a[i] != b[i]):
        if(ord(a[i])-ord(b[i]) < 0):
            c = -1
            break
        else:
            c = 1
            break
#print(a)
#print(b)
    
print(c)"""



"""for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = 0
    for i in range(1,n):
        if(a[i] != a[i-1]):
            b += abs(a[i]-a[i-1])-1
        else:
            continue
        

    print(b)"""


"""a = list(map(int, input().split()))
b = set(a)
b = list(b)
c = len(a)-len(b)
print(c)"""

def power(a):
    e = 0
    while(a > 0):
        r = a%10
        a = a//10
        e += r
    return e
"""for i in range(int(input())):
    n = int(input())
    c = 0
    d = 0
    for i in range(n):
        a, b = map(int, input().split())
        a = power(a)
        b = power(b)
        if(a > b):
            c += 1
        elif(a < b):
            d += 1
        else:
            c += 1
            d += 1
    if(c > d):
        print(0,c)
    elif(c < d):
        print(1,d)
    else:
        print(2,d)"""


"""for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = 0
    for i in range(n-1):
        if a[i] == a[i+1]:
            b += 1
    if b == n-1:
        print(*a)
    else:
        #c = 0
        #d = 0
        #for i in range(n-1):
         #   if(a[i+1]-a[i] <= 0):
          #      c += 1
           # elif(a[i+1]-a[i] >= 0):
            #    d += 1
        #e = (c-d)//2
        #if(e==0):
         #   print(a)
        #else:
         #  for i in range(e):
        for i in range(n):
            if(i%2 == 0):
                if(a[i] < 0):
                    a[i] = -a[i]
                else:
                    continue
            else:
                if(a[i] > 0):
                    a[i] = -a[i]
                else:
                    continue
        print(*a)"""


"""for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = sorted(a)
    c = a.copy()
    if(a == b):
        print("YES")
    else:
        i = 0
        while(len(a) > 1):
            if(i == 0 and a[i] < a[i+1]):
                if(a[i+1] < a[i+2]):
                    a.remove(a[i])
                    i = 0
                else:
                    if(a[i+1] > a[i+2] and a[i] > a[i+2]):
                        continue
                    else:
                        a.remove(a[i+1])
                        i = 0
            elif(i >= 1 and i < len(a)-1):
                if(a[i]<a[i+1] and (a[i-1]<a[i+1] or a[i+1]<a[i+2])):
                    a.remove(a[i])
                else:
                    a.remove(a[i+1])
            else:
                a.remove(a[i])
            i += 1
            if(i == n and len(a) != 1):
                break
                
        if(len(a) == 1):
            print("YES")
        else:
            print("NO")"""

"""n = int(input())
left = []
right = [0,1,2,3,4,5,6,7]
b = 0
g = 0
if(len(left) == 0):
    a = 0
    b = 1
    d = a
else:
    a = max(left)
if(len(right) == 0):
    c = n
    g = 1
    e = 0
else:
    c = min(right)
d = a-0
e = n-c
e = max(d,e)
print(e)"""


"""l1,s1,r1,p1 = map(int, input().split())
l2,s2,r2,p2 = map(int, input().split())
l3,s3,r3,p3 = map(int, input().split())
l4,s4,r4,p4 = map(int, input().split())
e = 0
if(p1 == 1):
    if(l1 == 1 or s1 == 1 or r1 == 1 or l2 == 1 or s3 == 1 or r4 == 1):
        e = 1
   
if(p2 == 1):
    if(l2 == 1 or s2 == 1 or r2 == 1 or l3 == 1 or s4 == 1 or r1 == 1):
        e = 1

   
if(p3 == 1):
    if(l3 == 1 or s3 == 1 or r3 == 1 or s1 == 1 or r2 == 1 or l4 == 1):
        e = 1
   
if(p4 == 1):
    if(l4 == 1 or s4 == 1 or r4 == 1 or l1 == 1 or s2 == 1 or r3 == 1):
        e = 1
   
if(e == 1):
    print("YES")
else:
    print("NO")"""


"""n = int(input())
a = 1000
i = 1
while(1):
  if(a >= n):
    b = a-n
    #print(b)
    break
  else:
    i += 1
    a = 1000*i
  
print(b)"""

"""n = int(input())
a = []
for i in range(n):
  s = input()
  a.append(s)
b,c,d,e = 0,0,0,0
for i in range(n):
  if(a[i] == 'AC'):
    b += 1
  elif(a[i] == 'WA'):
    c += 1
  elif(a[i] == 'TLE'):
    d += 1
  else:
    e += 1
print('AC', 'x', b)
print('WA', 'x', c)
print('TLE', 'x', d)
print('RE', 'x', e)"""

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
b = []
c = 0
for i in range(n+1):
  if(len(b) == 0):
      c += 0
  elif(len(b) == 1):
      c += b[0]
  elif(len(b) == n-1):
      c += min(b[-1],b[0])
      break
  else:
      c += min(b[-2],b[-1])
  b.append(a[i])
print(c)

#print(c)

  




    

    
    
    
        

    

"""c, v0, v1, a, l = map(int, input().split())
b = v0
c = c-b
d = 1
if c == 0:
    print(d)
else:
    i = 1
    while(c > 0):
        c = c+l
        b += i*a
        if b > v1:
            b = v1
        c -= b
        d += 1
    i += 1
    print(d)"""



"""for i in range(int(input())):
    n = int(input())
    a = ceil(n/2)
    print(a)"""


"""for i in range(int(input())):
    a, b, n, m = map(int, input().split())
    if(a+b < m+n):
        print("NO")
    elif(a > b):
       # if(m < n):
        b = b-m
        a = a-n
    #    else:
     #       a = a-m
      #      b = b-n
        if(b >= 0):
            print("YES")
        else:
            print("NO")
    else:
        if(a-m >= 0):
            print("YES")
        else:
            print("NO")"""
    


"""n = int(input())
a = list(map(int, input().split()))
b = []
c = 0
for i in range(n):
    if a[i] > 0:
        b.append(a[i])
    else:
        if len(b) == 0:
            c += 1
        else:
            d = b.pop()
            d -= 1
            if d > 0:
                b.append(d)
           
print(c)"""

            
    
            


"""s = input()
a = 0
b = 0
for i in s:
    if i.isupper():
        a += 1
    else:
        b += 1
if a > b:
    s = s.upper()
else:
    s = s.lower()
#print(a,b)
print(s)"""

"""a = [input()for _ in range(int(input()))]
b = 1
#a = ''.join(map(str,a))
#print(a)
i = 0
#while(i < len(a)-1):
for i in range(len(a)-1):
    if a[i] == a[i+1]:
        continue
    else:
        b += 1
#    i += 1
print(b)"""

    
    

    
    


"""n = int(input())
a = list(map(int, input().split()))
b = a.copy()
minb = 0
maxb = 0
mnxb = []
for i in range(n-1):
    if(a[i]<0 and i == 0):
        minb = abs(a[i]-a[i+1])
        maxb = abs(a[i]-a[n-1])
        mnxb.append((minb,maxb))
    elif(a[i]<0 and i>0):
        minb = min(abs(a[i]-a[i-1]),abs(a[i]-a[i+1]))
        maxb = max(abs(a[i]-a[n-1]),abs(a[i]-a[0]))
        mnxb.append((minb,maxb))
    elif(a[i]>0 and i == 0):
        minb = abs(a[i]-a[i+1])
        maxb = abs(a[i]-a[n-1])
        mnxb.append((minb,maxb))
    else:
        minb = min(abs(a[i]-a[i-1]),abs(a[i]-a[i+1]))
        maxb = max(abs(a[i]-a[n-1]),abs(a[i]-a[0]))
        mnxb.append((minb,maxb))
mnxb.append((abs(a[n-1]-a[n-2]),abs(a[n-1]-a[0])))
for i in range(n):
    print(*mnxb[i])"""


"""a = input()
b = input()
a = list(a)
b = list(b)
c = max(len(a), len(b))
d = 0
if(a == b):
    d = -1
    print(d)
else:
    if(len(a) > len(b)):
        print(len(a))
    elif(len(a) < len(b)):
        print(len(b))
    else:
        print(c)"""


"""n = int(inp())
a = list(map(int, inp().split()))
b = [0]*(n+1)
d = n
for i in range(n):
    b[a[i]] = 1
    while(b[d] and d>0):
        print(d,end=' ')
        d -= 1
    print()"""


"""n = int(input())
s = input()
b = set()
if(n < 26):
    print("NO")
else:
    for i in range(n):
        if s[i] not in b:
            if((s[i] == s[i].lower()) and (s[i].upper() not in b)):
                b.add(s[i])
            if((s[i] == s[i].upper()) and (s[i].lower() not in b)):
                b.add(s[i])
    if(len(b) == 26):
        print("YES")
    else:
        print("NO")"""


"""n = int(input())
a = list(map(int, input().split()))
b = [0]*(n+1)
for i in range(n):
    b[a[i]] += 1
c = max(b)
for i in range(len(b)):
    if(b[i] == c):
        print(i)
#print(b)
c = {}
count, itm = 0, ''
for item in reversed(a):
    c[item] = c.get(item,0)+1
    print(c[item])
    if c[item] >= count:
        count, itm = c[item],item
print(itm, count)

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


"""n = int(input())
a = list(map(int, input().split()))
b = 0
a.sort(reverse = True)
c = sum(a)
d = 0
for i in range(n):
    b += a[i]
    c -= a[i]
    d += 1
    if(b > c):
        break
print(d)"""


"""a = input()
b = input()
c = 'qwertyuiopasdfghjkl;zxcvbnm,./'
c = list(c)
b = list(b)
d = []
if(a == 'R'):
    for i in range(len(b)):
        for j in range(1,len(c)):
            if b[i] == c[j]:
                #print(c[j])
                e = j
                d.append(c[j-1])
                break
            
else:
    for i in range(len(b)):
        for j in range(len(c)-1):
            if b[i] == c[j]:
                e = j
                d.append(c[j+1])
                break
d = ''.join(map(str,d))
print(d)"""

    
"""for i in range(int(input())):
    n = int(input())
    if(n%4 == 0):
        print("YES")
    else:
        print("NO")"""


"""for i in range(int(input())):
    n = int(input())
    s = input()
    a = list(s)
    d = a.copy()
    if(a == sorted(a)):
        print(s)
    elif(a == sorted(a, reverse = True)):
        print('0')
    else:
        b = 0
        c = 0
        for i in range(n):
            if(a[i] == '0'):
                b += 1
            else:
                c += 1
        while(len(d) > 0):
            for i in range(len(d)-1):
                if((d[i] == '1' and d[i+1] == '0') and b>c):
                    a.remove(a[i+1])
                    b -= 1
                elif((d[i] == '1' and d[i+1] == '0') and b<=c):
                    a.remove(a[i])
                    c -= 1
                #print(a)
            d = a
            print(d)
            if((0<=b<=2 and 0<=c<=2) or (0<=b<=1 and 0<=c<=1)):
                break
        print(''.join(map(str,d)))"""


"""a = list(map(int, input().split()))
n = int(input())
b = {}
#for i in range(len(a)):
 #   b[a[i]] = i
#print(b)
#for i,num in enumerate(a):
#for i in range(len(a)):
  #  c = n-a[i]
 #   if c in b:
   #     j = b.get(c)
    #    print([i,j])
    #else:
     #   b[a[i]] = i
for i in range(len(a)):
    c = n-a[i]
    if c in b:
        print([i,b[c]])
    else:
        b[a[i]] = i
print(b)"""


"""a = list(map(int, input().split()))
n = int(input())
b = {}
for i in range(len(a)):
    b[i] = a[i]
print(b)
c = 0
for i in range(len(a)):
c = 0
for i in range(len(a)):
    for j in range(i+1, len(a)):
        d = a[i]
        print(d)
        d += a[j]
        print(d)
        c += 1
        if(d == n):
            break
print(c)"""


"""for i in range(int(input())):
    a, b, c = map(int, input().split())
    d = 0
    e = 0
    if(a > c//b and a >= c):
        d = -1
        e = b
    elif(a > c//b and a < c):
        d = 1
        e = b
    else:
        if(2*a % b != 0):
            d = 2*a
            e = -1
        else:
            d = (b-1)
            e = -1
    print(d,e)"""

"""for i in range(int(input())):
    s = input()
    a = list(s)
    b = 1
    if(len(a) == 2 and a[0] == a[1]):
        print("NET")
    elif(len(a) == 2 and a[0] != a[1]):
        print("DA")
    else:
        i = 0
        while(i < len(a)-1):
            if(a[i] != a[i+1]):
                b += 1
                a.pop(i)
                if(len(a) > 1):
                    a.pop(i)
                    i = 0
            else:
                i += 1
                continue
        if(b%2 == 0):
            print("DA")
        else:
            print("NET")"""


"""for i in range(int(input())):
    s, n = map(int, input().split())
    a = s%n
    b = s//n
    d = 0
    if(s%2 == 0):
        if(a == 0):
            d = b
        else:
            if(s < n):
                d = 1
            else:
                d = b+1
    else:
        if(s < n):
            s = s-1
            if(s > 0):
                d = 2
            else:
                d = 1
        else:
            s = s-b*n
            if(s == 1):
                d = b+s
            else:
                d = b+2
    print(d)"""

import operator
"""for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    b = set(a)
    b = list(b)
    b.sort()
    if a == b:
        print("YES")
        a.sort()
        print(*a)
    elif(a.count(a[-1]) > 1):
        print("NO")
    else:
        e = []
        #h = []
        #d = 1
        #g = 0
        c = {}
        d = 0
        for i in range(n):
            if a[i] in c:
                c[a[i]] += 1
                e.append(a[i])
            else:
                c[a[i]] = 1
        #print(c)
        
        e.sort(reverse = True)
        #print(e)
        
        #c = dict(c)
        #print(c)
        for i in c:
            if c[i] > 2:
                d = 1
        if d == 1:
            print("NO")
        else:
            print("YES")
            b = b+e
            print(*b)"""

"""for i in range(int(inp())):
    x, y, n = map(int, inp().split())
    a = ((n-y)//x)*x+y
    print(a)"""




    
"""for i in range(int(inp())):
    n = int(inp())
    a = 0
    if(n == 1):
        a = 0
    else:
        while(n > 1):
            if(n%6 == 0):
                n //= 6
                a += 1
            elif(2*n%6 == 0 and n%3 == 0):
                n *= 2
                a += 1
            else:
                 a = -1
                 break
    print(a)"""
open_list = ["("]
close_list = [")"]
def check(myStr): 
    stack = []
    e = 0
    for i in myStr: 
        if i in open_list: 
            stack.append(i) 
        elif i in close_list: 
            pos = close_list.index(i) 
            if ((len(stack) > 0)): #and
                #(open_list[pos] == stack[len(stack)-1])): 
                stack.pop()
                e += 1
            #else: 
             #   return -1
    #if len(stack) == 0: 
     #   return 0
    #else: 
     #   return -1
    return e


    
"""for i in range(int(input())):
    n = int(input())
    s = input()
    b = check(s)
    c = 0
    #print(b)
    if(b == n//2):
        c = 0
    else:
        c = (n-2*b)//2
    print(c)"""
    
    
    
    
"""path = input()
a = list(path)
b = [0]
b[0] = [0,0]
e = b.copy()
c = []
for i in range(len(a)):
    if a[i] == 'N':
        b[0][1] = b[0][1] + 1
        g = b[0]
        c.append(g)
        print(b[0])
        print(c)
    elif a[i] == 'S':
        b[0][1] = b[0][1] - 1
        g = b[0]
        c.append(g)
        print(b[0])
        print(c)
    elif a[i] == 'E':
        b[0][0] = b[0][0] + 1
        g = b[0]
        c.append(g)
        print(b[0])
        print(c)
    else:
        b[0][0] = b[0][0] -1
        g = b[0]
        c.append(g)
        print(b[0])
        print(c)
print(c)"""
                
            
    
        


    
        
                

"""n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m-1):"""

"""n = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
b = []
s = ''
for i in range(n):
    s = str(a[i])
    for j in range(n):
        if(i != j):
            s += str(a[j])
    b.append(int(s))
    s = ''
b = set(b)
b = list(b)
print(max(b))"""


        
    
"""n = int(input())
a = list(map(int, input().split()))
b = [0]*n
c = [0]*n
b[0] = 1
for i in range(1, n):
    if(a[i] >= a[i-1]):
        b[i] = b[i-1] + 1
    else:
        b[i] = 1
c[n-1] = 1
for i in range(n-2,-1,-1):
    if(a[i] >= a[i-1]):
        c[i] = c[i+1]+1
    else:
        c[i] = 1
mx = 0
for i in range(n):
    mx = max(mx, b[i]+c[i]-1)
print(mx)"""

    


    
"""for i in range(int(inp())):
    n = int(inp())
    a = 0
    if(n == 1):
        a = 0
    while(n > 1):
        if(n%oddn(n) == 0):
            #print(oddn(n))
            n = n//(oddn(n))
            a += 1
        else:
            n = n-1
            a += 1
    if(a == 0):
        print("FastestFinger")
    elif(a%2 != 0):
        print("Ashishgup")
    else:
        print("FastestFinger")"""


"""for i in range(int(inp())):
    n = int(inp())
    a = list(map(int, inp().split()))
    e_i = []
    o_i = []
    for i in range(len(a)):
        if(a[i]%2 == 0):
            e_i.append(i+1)
            
        else:
            o_i.append(i+1)
    index_list = []
    if(len(e_i)%2 == 0 and len(o_i)%2 == 0):"""


"""n, start = map(int, inp().split())
nums = []
for i in range(n):
    nums.append(start + 2*i)
xor_nums = 0
for i in range(n):
    xor_nums = xor_nums^nums[i]
print(xor_nums)"""


    
"""for i in range(int(inp())):
    n = int(inp())
    a = 0
    #while(n >= 1):
    if(n%2 == 0):
        a = n//2
    else:
        #a.append(gcd(n-1,(n-1)//2))
        a = (n-1)//2
        #if(n%3 == 0):
            #a.append(gcd(n,n//3))
        #if(n%5 == 0):
            #a.append(gcd(n,n//5))
        #if(n%7 == 0):
            #a.append(gcd(n,n//7))
        #n -= 1
    print(a)"""
    
            

"""for i in range(int(input())):
    s = input()
    a = 0
    b = 0
    for i in range(len(s)):
        if(s[i] == '0'):
            a += 1
        else:
            b += 1
    pre_0 = [0]*len(s)
    pre_1 = [0]*len(s)
    if(s[0] == '0'):
        pre_0[0] = 1
        pre_1[0] = 0
    else:
        pre_0[0] = 0
        pre_1[0] = 1
    #print(pre_0[0])
    #print(pre_1[0])
    for i in range(1,len(s)):
        if(s[i] == '0'):
            pre_0[i] = pre_0[i-1]+1
            pre_1[i] = pre_1[i-1]
        else:
            pre_0[i] = pre_0[i-1]
            pre_1[i] = pre_1[i-1]+1
    #print(pre_0)
    #print(pre_1)
    e = sys.maxsize
    for i in range(len(s)):
        e = min(e, pre_0[i]+(b-pre_1[i]))
        e = min(e, pre_1[i]+(a-pre_0[i]))
    print(e)"""
    
    
              


"""for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = []
    for i in range(n):
        c.append([a[i],b[i]])
    #print(c)
    c = sorted(c,key=lambda c:c[1])
    #print(c)
    d = []
    e = []
    for i in range(len(c)):
        d.append(c[i][0])
        e.append(c[i][1])
    #print(d)
    #print(e)
    g = []
    i = 0
    g.append(
    for j in range(1,n):
        if(d[j] >= e[i]):
            g.append(j+1)
            i = j
    print(*g)"""


"""for i in range(int(input())):
    a, b, n = map(int, input().split())
    d = []
    c = b
    e = []
    g = a
    h = b
    for i in range(n):
        b = a
        a += c
        c = b
        d.append(a)
        if(a > n):
            break
    for i in range(n):
        a = h
        h += g
        g = a
        e.append(h)
        if(h > n):
            break
        
    #print(d)
    #print(len(d))
    #print(e)
    print(min(len(e), len(d)))"""
    
    
    
    
    
        
    
    

    
        
    

"""for i in range(int(input())):
    n, s, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = 1
    r = n
    b = 0
    c = n
    while(l <= r):
        m = (l+r)//2
        if m not in a and (abs(s-m)<=m//2+s):
            b = m
            #c = abs(s-m)
            r = m-1
        else:
            l = m+1
    print(abs(s-b))"""
    

"""for i in range(int(inp())):
    s = inp()
    a = list(s)
    b = []
    for i in range(len(a)):
        c = int(a[i])*(10**(len(a)-i-1))
        #print(c)
        if(c > 0):
            b.append(c)
    print(len(b))
    print(*b)"""
    
    
    
    
    
    


"""for i in range(int(inp())):
    a1, b1 = list(map(int, inp().split()))
    a2, b2 = list(map(int, inp().split()))
    a = min(a1, b1)
    b = min(a2, b2)
    c = a+b
    d = max(a1, b1)
    e = max(a2, b2)
    if(d != e):
        print("NO")
    else:
        if(c == d and c == e):
            print("YES")
        else:
            print("NO")"""
            
    


"""s = inp()
a = list(s)
b = {}
c = ''
for i in a:
    if i in b:
        b[i] += 1
    else:
        b[i] = 1
for key,val in b.items():
    if(val == 1):
        c = key
        break
#print(b)
print(c)"""


"""s = inp()
b = counter(s)
a = ''
print(str(b))
for key,val in b.items():
    if(val == 1):
        a = key
        break
if(a == ''):
    print(s[0])
else:
    print(a)"""
    




"""for i in range(int(inp())):
    n, k = map(int, inp().split())
    s = inp()
    a = list(s)
    b = []
    c = []
    d = []
    g = []
    e = 0
    h = 0
    l = 0
    for i in range(n):
        if(a[i] == '1'):
            b.append(i)
    #print(b)
    if(len(b) == 0):
        if(n%2 == 0):
            e = n//(k+1)
        else:
            e = 1 + n//(k+1)
    elif(len(b) == 1):
        d = a[:len(b)+1]
        g = a[len(b):]
        #print(d)
        #print(g)
        for i in range(len(d)):
            if(d[i] == '0'):
                h += 1
        for i in range(len(g)):
            if(g[i] == '0'):
                l += 1
        if(h>0 and l>0 and (h//(k+1) >= k or l//(k+1) >= k)):
            e = h//(k+1) + l//(k+1)
        elif(l>0 and l//((k+1)>=k)):
             e = l//(k+1)
        else:
             e = h//(k+1)
        
                
        #else:
            #if(n//(k+1) >= k):
                #e = n//(k+1)
        
    else:
        for i in range(len(b)-1):
            c = a[b[i]:b[i+1]+1]
            #print(c)
            d = len(c)-2
            if(k == 1):
                e += (d-1)//(k+1)
            else:
                if((d-1)//(k+1) >= k):
                    e += d//(k+1)
    print(e)"""
    
                


"""for i in range(int(inp())):
    a = inp()
    b = list(a)
    c = []
    c.append(b[0])
    #c = b.copy()
    for i in range(1,len(b), 2):
            c.append(b[i])
            #print(c)
        #if(c[-1] != b[-1]):
    #c.append(b[-1])
    c = ''.join(map(str, c))
    out(c)
    nextline()"""
    
    

"""for i in range(int(inp())):
    n = int(inp())
    a = list(map(int, inp().split()))
    o = 0
    e = 0
    b = 0
    if(n%2 == 0):
        for i in range(n):
            if(a[i]%2 == 0):
                e += 1
            else:
                o += 1
        #print(e,o)
        if(e == o):
            for i in range(n):
                if((a[i]%2 == 0 and i%2 == 0)or (a[i]%2 != 0 and i%2 != 0)):
                   pass
                else:
                   b += 1
        else:
            b = -1
    else:
        for i in range(n):
            if(a[i]%2 == 0):
                e += 1
            else:
                o += 1
        #print(e,o)
        if(e%2 != o%2 and e-o==1):
            if(n > 1 and e>=1 and o>=1):
                for i in range(n):
                    if((a[i]%2 == 0 and i%2 == 0)or (a[i]%2 != 0 and i%2 != 0)):
                       pass
                    else:
                       b += 1
            elif(n == 1 and e == 1):
                b = 0
            else:
                b = -1
        else:
            b = -1
    if(b<0):
        print(b)
    else:
        print(b//2)"""
        
            
            
            
            


"""for i in range(int(input())):
    n, k = map(int, input().split())
    a = floor((k-1)/(n-1))+k
    print(a)"""

"""for i in range(int(input())):
    n, k = map(int, input().split())
    l = 1
    r = 2*k
    a = 0
    while( l <= r):
        m = (l+r)//2
        if(m-m//n >= k):
            a = m
            r = m-1
        else:
            l = m+1
    print(a)"""
    
    

"""n, m = list(map(int, input().split()))
xc, yc = list(map(int, input().split()))
k = int(input())
a = 0
for i in range(k):
    dx, dy = map(int, input().split())
    #c.append([dx,dy])
    #c.append(dy)
    #d.append(c)
    #c.pop()
    #c.pop()
    l = 0
    r = 10**9
    b = 0
    while(l <= r):
        mid = (l+r)//2
        if(1 <= xc+dx*mid <= n and 1<= yc+dy*mid <= m):
            b = mid
            l = mid+1
        else:
            r = mid-1
    xc = xc+dx*b
    yc = yc+dy*b
    a += b
print(a)"""

    

    


"""n, a = map(int, input().split())
b = list(map(int, str(n)))
for i in range(a):
    if(b[-1] == 0):
        b.pop()
    else:
        b[-1] = b[-1] - 1
print(''.join(map(str,b)))"""

"""n = int(input())
s = input()
a = list(s)
b = 0
for i in range(n-1):
    if(a[i] == a[i+1]):
        b += 1
print(b)"""

"""s = input()
a = list(s)
b = 1
c = 1
d = 0
e = 0
h = 0
m = 1000000007
if 'c' in a or 'k' in a:
    d = 0
else:
    for i in range(len(a)-1):
        if(a[i] == 'g' and a[i+1] == 'g'):
            b += 1
        if(a[i] == 'f' and a[i+1] == 'f'):
            c += 1
    if(b == 1 and c == 1):
        for i in range(len(a)):
            if(a[i] == 'g'):
                e += 1
            if(a[i] == 'f'):
                h += 1
        if(e == 1 and h == 1):
            d = 1
        else:
            d = e%m + h%m
    elif(b == 1):
        b = 0
        d = b%m + c%m
    elif(c == 1):
        c = 0
        d = b%m + c%m
    else:
        d = b%m * c%m
print(d)
#print(b,c)"""



"""n, k = map(int, input().split())
l = 0
r = n-1
c = 0
while(l <= r):
    m = (l+r)//2
    a = m*(m+1)//2
    b = n-m
    if(a-b == k):
        c = b
        break
    elif(a-b > k):
        r = m-1
    else:
        l = m+1
        #b = a - k
        #print(b,b+m)
        #print(m)
        #if(b+m == n):
            #break
print(c)"""



"""for i in range(int(input())):
    n = int(input())
    a = []
    b = []
    c = n//2
    if(c%2 != 0):
        print("NO")
    else:
        for i in range(1,n+1):
            if(i%2 == 0):
                a.append(i)
        #print(a)
        for i in range(1,a[len(a)-2]):
            if(i%2 != 0):
                b.append(i)
        d = sum(a)-sum(b)
        #print(b)
        if(d%2 != 0):
            b.append(d)
            print("YES")
            print(*(a+b))
        else:
            print("NO")"""
        
            
        


"""for i in range(int(input())):
    n = int(input())
    a = n//2
    s = 8*((a*(a+1)*(2*a+1))//6)
    print(s)"""
    


"""for i in range(int(input())):
    n, s, k = map(int, input().split())
    a = list(map(int, input().split()))
    a = set(a)
    d = 10^5
    e = 10^5
    if s in a:
        b = [x for x in range(1,s)]
        c = [x for x in range(s+1,n+1)]
        c.sort(reverse = True)
        #print(b)
        #print(c)
        if(len(b) == 0):
            for i in range(k):
                if min(c) in a:
                    c.pop()
                    if(len(c) == 0):
                        break
                else:
                    e = min(c)-s
                    break
        elif(len(c) == 0):
            for i in range(k):
                if max(b) in a:
                    b.pop()
                    if(len(b) == 0):
                        break
                else:
                    d = s-max(b)
                    break
        else:
            for i in range(k):
                if max(b) in a:
                    b.pop()
                    if(len(b) == 0):
                        break
                else:
                    d = s-max(b)
                    break
            for i in range(k):
                if min(c) in a:
                    c.pop()
                    if(len(c) == 0):
                        break
                else:
                    e = min(c)-s
                    break
        print(min(d,e))
    else:
        print(0)"""
    
    


"""n = int(input())
m = int(input())
a = []
for i in range(n):
    a.append(int(input()))
kmax = max(a)+m
a.sort()
for i in range(m):
    a[0] = a[0] + 1
    a.sort()
#print(a)
print(max(a), kmax)"""




"""for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = set(a)
    c = 1
    d = []
    a.sort()
    if(len(a) == 1):
        e = 0
    else:
        if(a == list(b)):
            e = 1
        else:
            #for i in range(n):
                #d[a[i]] += 1
            #for i in range(len(d)):
                #if(d[i] > 1 and d[i]%2 == 0):
                    #c += 1
            #print(d)
            for i in range(n-1):
                if(a[i] == a[i+1]):
                    c += 1
                elif(c == 1):
                    pass
                else:
                    d.append(c)
                    c = 1
            if(c>1):
                d.append(c)
            #print(d)
            #if(max(d) == 1):
                #e = 2
            #elif(max(d) == 2):
                #e = max(d)+1
            #else:
            e = max(min(len(b)-1,max(d)),min(len(b),max(d)-1))
    print(e)"""
    
        


"""n, k = map(int, input().split())
l = []
d = 0
for i in range(n):
    a,b = map(int, input().split())
    l.append((a,-b))
#a = sorted(a,key=lambda a: (a[0],a[1]))
l.sort(reverse = True)
#print(l)
c = l[k-1]
#print(c)
for i in range(n):
    if(l[i] == c):
        d += 1
print(d)"""




"""n, k = map(int, input().split())
a = 240
b = a-k
c = 0
d = []
for i in range(1,n+1):
    c += 5*i
    if(b-c >= 0):
        #print(b-c)
        d.append(i)
#print(d)
if(len(d) == 0):
    d.append(0)
print(max(d))"""




"""for i in range(int(input())):
    n = int(input())
    for i in range(2,30):
        b = 2**i - 1
        if(n%b == 0):
            d = n//b
    print(d)"""



"""for i in range(int(input())):
    n, x, m = map(int, input().split())
    a = x
    b = x
    for i in range(m):
        l, r = map(int, input().split())
        if(l <= a <= r):
            a = l
        if(l <= b <= r):
            b = r
    print(b-a+1)"""
    
                
                


"""for i in range(int(input())):
    a, b = map(int, input().split())
    if(a == 0 or b == 0):
        c = 0
    else:
        c = a+b
    d = min(c//3, min(a,b))
    print(d)"""



"""n = int(input())
a = list(map(int, input().split()))
b = 1
e = []
for i in range(n-1):
    if(a[i] == a[i+1]):
        b += 1
    else:
        e.append(b)
        b = 1
e.append(b)
print(e)
h = 0
for i in range(len(e)-1):
    h = max(h,min(e[i],e[i+1]))
print(2*h)"""



"""a, b, c = map(int, input().split())
#e = max(a,b,c)
for i in range(1,a*c):
    if(a*c - i*b <= b*c):
        d = i
        break
print(d)"""



"""for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    b = []
    #b = a[-1] - a[0]
    for i in range(n):
        for j in range(i+1, n):
            b.append(a[j]-a[i])
    print(min(b))"""
     


"""for i in range(int(input())):
    a, b = map(int, input().split())
    if(a<b):
        a, b = b, a
    c = 4*b**2
    if(2*b < a):
        c = a**2
    print(c)"""

    
    


"""n=int(input())
l=[int(i) for i in input().split()]
s=list(input())
sm=0 
for i in range(n):
    if s[i]=='B': 
        sm+=l[i]
        l[i]=-l[i]
print(l)
maxi1=0 
sm1=0 
for i in range(n):
    sm1+=l[i]
    maxi1=max(maxi1,sm1)
sm2=0 
maxi2=0 
for i in range(n-1,-1,-1):
    sm2+=l[i]
    maxi2=max(maxi2,sm2)
print(sm2)
print(maxi1,maxi2)
print(sm+max(maxi1,maxi2))"""


"""n = int(input())
a = list(map(int, input().split()))
b = input()
b = list(b)
d = 0
h = []
l = []
if(n == 1):
    h.append(a[0])
else:
    for i in range(n):
        if(b[i] == 'A'):
            d += 1
    if(d == n):
        h.append(sum(e))
    else:
        for i in range(n-1, -1, -1):
            if(b[i] == 'B'):
                h.append(a[i])
            elif(b[i] == 'A'):
                l.append(a[i])
                #h.append(i+1)
                #break
            else:
                pass
        h.append(max(l))
print(sum(h))"""


        


        
    


"""for i in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = sum(a)
    if(m <= b):
        print(m)
    else:
        print(b)"""
    



"""n = int(input())
a = input()
a = list(a)
b = []
d = 0
e = 1
if(len(a) == 1):
    if(a[0] == '0'):
        e = 0
else:
    for i in range(n):
        if(a[i] == '1'):
            b.append(i)
    if((a[0] == '0' and a[1] == '0') or (a[-1] == '0' and a[-2] == '0')):
        e = 0
    else:
        for i in range(len(b)-1):
            for j in range(b[i], b[i+1]+1):
                #print(j)
                #print(a[j])
                if(a[j] == '0'):
                    d += 1
            #print(d)
            if(d > 2 or d == 0):
                e = 0
                break
            d = 0
if(e == 1):
    print("Yes")
else:
    print("No")

            
#print(b)"""


"""n = int(input())
a = list(map(int, input().split()))
b = 0
d = 0
e = 0
o = 0
g = []
h = []
m = []
for i in range(n):
    if(a[i]<0):
        b += 1
    elif(a[i]>0):
        d += 1
    else:
        e += 1
for i in range(n):
    if(b%2 == 1):
        if(a[i] < 0 and len(g) == 0):
            g.append(a[i])
        elif(a[i] > 0 or a[i] < 0):
            h.append(a[i])
        else:
            m.append(a[i])
    elif(b%2 == 0):
        if(a[i]<0 and len(g) == 0):
            g.append(a[i])
        elif(a[i]<0):
            if(d == 0):
                h.append(a[i])
            else:
                m.append(a[i])
        elif(a[i]>0):
            h.append(a[i])
        else:
            m.append(a[i])
    #if(a[i] == 0):
        #m.append(a[i])
if(d == 0 and len(h)%2 != 0):
    o = h.pop()
    m.append(o)
print(len(g),*g)
print(len(h),*h)
print(len(m),*m)"""
    


"""n, m, k = map(int, input().split())
a = []
b = []
d = 0
e = 0
for i in range(m+1):
    x = int(input())
    a.append(x)
for i in range(m):
    b.append(bin(a[-1]^a[i]).replace("0b",""))
#print(b)
for i in b:
    c = list(i)
    #print(c)
    for j in range(len(c)):
        if(c[j] == '1'):
            d += 1
    #print(d)
    if(d <= k):
        e += 1
    d = 0
        
print(e)
#print(a)"""



"""a, b = map(int, input().split())
c = a+b
d = 0
e = 0
if(a == 0 and b == 0):
    print("NO")
else:
    if(c%2 == 0):
        d = c//2
        e = c//2
    else:
        d = c//2
        e = c//2+1
    if(a == d or a == e and b == e or b == d):
        print("YES")
    else:
        print("NO")"""
    


"""n, m = map(int, input().split())
a = []
b = []
d = []
e = 0
for i in range(n):
    s = input()
    s = list(s)
    a.append(s)
for i in range(len(a)):
    for j in range(i+1, len(a)):
        if(a[i] == a[j][::-1]):
            if(len(b) == 0):
                b.insert(0,''.join(map(str,a[i])))
                b.insert(1,''.join(map(str,a[j])))
            else:
                b.insert(0,''.join(map(str,a[i])))
                b.insert(len(b),''.join(map(str,a[j])))
    #print(b)
    if(len(a[i])%2 == 0):
        if(a[i][:len(a[i])//2] == a[i][len(a[i])//2:][::-1]):
            e = 1
            if(len(d) == 0):
                b.insert(len(b)//2,''.join(map(str,a[i])))
                d.append(''.join(map(str,a[i])))
                #break
            #else:
                #b.insert(0,''.join(map(str,a[i])))
                #d.append(''.join(map(str,a[i])))
    else:
        if(a[i][:len(a[i])//2+1] == a[i][len(a[i])//2:][::-1]):
            e = 1
            if(len(d) == 0):
                b.insert(len(b)//2,''.join(map(str,a[i])))
                d.append(''.join(map(str,a[i])))
                #break
            #else:
                #b.insert(0,''.join(map(str,a[i])))
                #d.append(''.join(map(str,a[i])))
                
print(len(''.join(map(str,b))))
print(''.join(map(str,b)))
#print(d)
#print(e)
#print(a)"""




"""s = input()
s = list(s)
a = []
b = []
d = 0
if(len(s)%2 == 0):
    a.append(s[:len(s)//2])
    b.append(s[len(s)//2:])
else:
    a.append(s[:len(s)//2+1])
    b.append(s[len(s)//2:])
#b = b[::-1]
a = sum(a,[])
b = sum(b,[])
#print(a)
#print(b)
for i in range(len(a)):
    if(a[i] != b[len(a)-i-1]):
        d += 1
        #print(a[i])
        #print(b[len(a)-1-i])
    #else:
        #print(a[i])
        #print(b[len(a)-i-1])
#print(d)
if(d == 1 and len(s)%2 == 0):
    print("YES")
elif(d == 0 and len(s)%2 == 0):
    print("NO")
elif((d == 0 or d == 1) and len(s)%2!=0):
    print("YES")
else:
    print("NO")"""


    
    
    


"""n, k = map(int, input().split())
a = list(map(int, input().split()))
i = 1
while(k-i > 0):
    k -= i
    i += 1

#b = []
#for i in range(1,n+1):
    #b.append(a[0:i])
#b = sum(b,[])
#print(b)
print(a[k-1])"""



"""n = int(input())
a = 0
b = 0
d = n%7
if(d == 0):
    e = n//7
    a = 2*e
    b = 2*e
else:
    if(n<7):
        if(d == 1):
            a = 0
            b = 1
        elif(d > 1 and d < 6):
            a = 0
            b = 2
        else:
            a = 1
            b = 2
    else:
        e = n//7
        a = 2*e
        b = 2*e
        if(d == 1):
            b += 1
        elif(d<6):
            b += 2
        else:
            a += 1
            b += 2
print(a, b)""" 


"""for i in range(int(input())):
    n, m = list(map(int, input().split()))
    a = [[int(x) for x in input().split()] for _ in range(n)]
    r = set()
    c = set()
    #print(a)
    for i in range(n):
        for j in range(m):
            if(a[i][j] == 1):
                r.add(i)
                c.add(j)
    b = min(n-len(r), m-len(c))
    
    if(b%2 == 0):
        print("Vivek")
    else:
        print("Ashish")"""


"""for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    d = 0
    e = 0
    g = 0
    c = sorted(a)
    if(a == c):
        d = 1
    else:
        for i in range(n):
            if(b[i] == 0):
                e += 1
            else:
                g += 1
    if(e and g):
        d = 1
    if(d == 1):
        print("Yes")
    else:
        print("No")"""
    
    
    
    
"""def createMatrix(rowCount, colCount, dataList):   
    mat = []
    for i in range (rowCount):
        rowList = []
        for j in range (colCount):
            if dataList[j] not in mat:
                rowList.append(dataList[j])
        mat.append(rowList)

    return mat 

    
for i in range(int(input())):
    n = int(input())
    r = n
    c = n
    a = [x for x in range(1,n**2+1)]
    m = createMatrix(r,c,a)
    if(n == 2):
        for i in range(n):
            for j in range(n-1):
                if(i%2 != 0):
                    m[i][j], m[i][n-1-j] = m[i][n-1-j], m[i][j]
    else:
        for i in range(n):
            for j in range(n-2):
                if(i%2 != 0):
                    m[i][j], m[i][n-1-j] = m[i][n-1-j], m[i][j]
                #if((m[i][j] + m[n-1-i][n-1-j])%2 != 0):
                    #m[n-1-i][n-1-j], m[n-1-i][n-1-j-1] = m[n-1-i][n-1-j-1], m[n-1-i][n-1-j]
                #else:
                    #m[n-1-i][n-1-j], m[n-1-i][n-1-j-1] = m[n-1-i][n-1-j-1], m[n-1-i][n-1-j]
    for i in range(n):
        for j in range(n):
            print(m[i][j], end=' ')
        print( )"""
    
    
    
    
            
    
    
        


"""for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = 0
    c = 0
    d = 1
    e = 0
    if(len(a) == 1):
        if(a[0] == 5):
            d = 1
        else:
            d = 0
    else:
        #b.append(a[0])
        for i in range(1, n):
            if(a[i] == 10):
                c += 1
                if(b > 0):
                    b = b-1
                else:
                    d = 0
                    break
                #if(a[i] - b <= 5):
                    #b.append(a[i] - sum(b))
                    #b += a[i]-5
            elif(a[i] == 15):
                e += 1
                if(c > 0):
                    c = c-1
                elif(b > 1):
                    b = b-2
                else:
                    d = 0
                    break
            else:
                #b = b + a[i]
                b += 1
                    
        
    #if(e == 0):
        #if(c <= b and c>=1 and b>=1):
            #d = 1
        #else:
            #d = 0
    #else:
        #if(e<=c and c<=b and c>=1 and b>=1):
            #d = 1
        #else:
            #d = 0
    if(d == 1):
        print("YES")
    else:
        print("NO")"""
    
    
    


"""for i in range(int(input())):
    s = input()
    a = 0
    s = list(s)
    j = 1
    for i in range(0, len(s)-1):
    #while(len(s) != 0):
        if(len(s) == 0):
            break
        if((s[i] =='x' and s[i+1] == 'y') or (s[i] == 'y' and s[i+1] == 'x')):
            a += 1
            s[i+1] = 'z'
            #print('a')
            #print(j)
        #else:
            #j -= 1
            #print(j)
            #s.remove(i)
            #s.remove(i+1)
            #if(len(s) == 0):
                #break
    print(a)"""
    
    

"""for i in range(int(input())):
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    a = 0
    for i in range(n):
        if(p[i] > k):
            a += p[i] - k
    print(a)"""


"""for i in range(int(input())):
    ts = int(input())
    a = 0
    b = 0
    if(ts == 1):
        b = 0
    else:
        if(ts%2 != 0):
            a = ts//2+1
            b = ts-a
        else:
            d = 0
            while(ts%2 == 0):
                d += 1
                ts = ts//2
            if(ts%2 != 0):
                a = ts//2+1
                b = ts-a
    print(b)"""
    

"""for i in range(int(input())):
    n = int(input())
    s = list(map(int, input().split()))
    a = []
    c = []
    s.sort()
    for k in range(1,1024):
        for i in s:
            b = i^k
            a.append(b)
        #print(a)
        #print(s)
        if(s == sorted(a)):
            c.append(k)
        a.clear()
    if(len(c) == 0):
        c.append(-1)
    print(min(c))"""
    
            


"""for i in range(int(input())):
    a, b = map(int, input().split())
    c = 0
    if(a == b):
        c = 0
    elif(a > b):
        d = a/b
        if(d == a//b):
            if(d == 1 and a == b):
                c = 0
            elif(d == 2 or d == 4 or d == 8):
                c = 1
            elif(d > 8 and d%2 == 0):
                while(d != 1):
                    if(d%8 == 0):
                        d = d//8
                        c += 1
                    elif(d%4 == 0):
                        d = d//4
                        c += 1
                    elif(d%2 == 0):
                        d = d//2
                        c += 1
                    else:
                        c = -1
                        break
            else:
                c = -1
        else:
            c = -1
    else:
        d = b/a
        if(d == b//a):
            if(d == 1 and b == a):
                c = 0
            elif(d == 2 or d == 4 or d == 8):
                c = 1
            elif(d > 8 and d%2 == 0):
                while(d != 1):
                    if(d%8 == 0):
                        d = d//8
                        c += 1
                    elif(d%4 == 0):
                        d = d//4
                        c += 1
                    elif(d%2 == 0):
                        d = d//2
                        c += 1
                    else:
                        c = -1
                        break
            else:
                c = -1
        else:
            c = -1
    print(c)"""
    
        
        


"""for i in range(int(input())):
    s = input()
    a = list(s)
    d = ['0', '1', '0']
    e = ['1', '0', '1']
    b = 0
    if(len(a) < 3):
        b = 0
    elif(len(a) == 3):
        if(a != d and a != e):
            b = 0
        else:
            b = 1
    else:
        g = 0
        h = 0
        for i in a:
            if(i == '0'):
                g += 1
            else:
                h += 1
        if(g <= 1 or h <= 1):
            b = 0
        if(g < h):
            b = g
        else:
            b = h
    print(b)"""
    
        


"""for i in range(int(input())):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    b = 0
    c = 0
    d = 0
    if(len(a) == 1):
        if(a[0]%2 == 0):
            b = 0
        else:
            b = 1
    else:
        for i in a:
            if(i%2 == 0):
                c += 1
            else:
                d += 1
        if(x < c+d):
            if(c and d > 1):
                b = 1
            elif(c == 0 and x%2 == 0):
                b = 0
            elif(d == 0):
                b = 0
            else:
                b = 1
        else:
            #if(x%2 == 0):
            if(d%2 != 0):
                b = 1
            else:
                b = 0
    if(b == 0):
        print("No")
    else:
        print("Yes")"""
    #print(b)
    
            


#import math
"""for i in range(int(input())):
    n, m, k = map(int, input().split())
    c = n//k
    if(m == 0):
        d = 0
    elif(m <= c):
        d = m
    else:
        d = (m-c)//(k-1)
        if((m-c)%(k-1) != 0):
            d += 1
        d = c - d
            #d = c - math.ceil((m-c)/(k-1))
        #else:
            #d = c - 1
        #if(d < 0):
            #d = 0
    print(d)"""


"""def min(n,m):
    if(n%2 == 0 and m%2 == 0):
        b = n*(m//2)
    elif(n%2 == 0 and m%2 != 0):
        b = (n*(m//2))+n//2
    elif(n%2 != 0 and m%2 == 0):
        b = n*(m//2)
    else:
        b = (n*(m//2)) + (n-(n//2))
    return(b)
    


for i in range(int(input())):
    n, m = map(int, input().split())
    print(min(n,m))"""
    



"""from collections import defaultdict

def smallest(s1, s2):
    assert s2 != ''
    d = defaultdict(int)
    nneg = [0]  
    def incr(c):
        d[c] += 1
        if d[c] == 0:
            nneg[0] -= 1
    def decr(c):
        if d[c] == 0:
            nneg[0] += 1
        d[c] -= 1
    for c in s2:
        decr(c)
    minlen = len(s1) + 1
    j = 0
    for i in range(len(s1)):
        while nneg[0] > 0:
            if j >= len(s1):
                return minlen
            incr(s1[j])
            j += 1
        minlen = min(minlen, j - i)
        decr(s1[i])
    return minlen
    
# ans = smallest("12222133333332", "123")
# print(ans)

for i in range(int(input())):
    s1= input()
    e = 0
    g = 0
    h = 0
    for i in range(len(s1)):
        if(s1[i] == '1'):
            e += 1
        elif(s1[i] == '2'):
            g += 1
        elif(s1[i] == '3'):
            h += 1
    s2="123"
    
    if(e < 1 or g < 1 or h < 1):
        ans = 0
    else:
        ans= smallest(s1, s2)
    print(ans)"""


"""for i in range(int(input())):
    a, b, c, d = map(int, input().split())
    r = b
    ans = 0
    if(b < a and c < d):
        ans = -1
    else:
        i = 0
        while(r < a):
            r += c - d
            i += 1
        if(i == 0):
            ans = b
        else:
            ans = b + i*c
    print(ans)           

if(d >= c && a >b)
            cout << -1 << endl;
            continue;
        }
        if(a <= b){
            cout << b << endl;
            continue;
        }
        a -= b;
        long int q = c-d;
        if(a % q == 0)
        {
            cout << ((a/q)*c)+b << endl;
        }else{
            cout << (((a/q)+1)*c)+b << endl;
        }"""
"""for i in range(int(input())):
    n = int(input())
    s = list(map(int, input().split()))
    s.sort()
    c = 0
    p = 1
    if(n == 1):
        c = 1
    else:
        
        for i in range(n):
            if(s[i] <= p):
                c += 1
                p = p - s[i] + 1
            else:
                p = p + 1
    print(c)"""



"""res = False
def chkList(lst):
    if len(lst) < 0 : 
        res = True
    res = all(ele == lst[0] for ele in lst)
    return(res)



for i in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    p = l.copy()
    c = 0
    d = []
    if(chkList(l) == True):
        h = len(l)
    else:
        
        h = len(l)
    print(h)"""


"""for i in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()
    l.reverse()
    #print(l)
    res = 0
    p = 0
    while(True):
        res += 1
        p = p + l[p]
        if(p >= n):
            break
    print(res)"""
    
"""7017173017"""