Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def divisors(n):
    m = 1
    divs = []
    while m * m <= n:
        if n % m == 0:
            divs.append(m)
            if n != m * m:
                divs.append(n // m)
        m += 1
    divs.sort()
    return divs


N, *A = map(int, read().split())

cnt = 0

for i, a in enumerate(A):
    divs = divisors(a)
    if len(set(set(divs) & (set(A[:i]) | set(A[i + 1:])))) == 0:
        cnt += 1

print(cnt)


### FIXED CODE ###

#! /usr/bin/env python3

import sys
from math import gcd
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, *A = map(int, read().split())
A = sorted(A)
M = pow(10, 6) + 1
divs = [False] * M
cnt = 0
for i, a in enumerate(A):
    if divs[a]:
        continue

    if i == N - 1 or a != A[i + 1]:
        cnt += 1

    acc = a
    while acc < M:
        divs[acc] = True
        acc += a
print(cnt)
### BUGGY CODE ###

def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    b=[[0]*(k+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":
            if int(y)%kk<k:
                b[int(x)%kk+1][int(y)%k+1]+=1
            else:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
        else:
            if int(y)%kk<k:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
            else:
                b[int(x)%kk+1][int(y)%k+1]+=1
    b=[list(ac(i)) for i in b]
    for i in range(1,kk+1):
        for j in range(k+1):
            b[i][j]+=b[i-1][j]
    ans=0
    for i in range(kk):
        if i==0:
            a_t=((i,i+k,0),(i+k,kk,1))
        elif i<k:
            a_t=((0,i,-1),(i,i+k,0),(i+k,kk,1))
        elif i==k:
            a_t=((0,i,-1),(i,kk,0))
        else:
            a_t=((0,i-k,-2),(i-k,i,-1),(i,kk,0))
        for j in range(k):
            if j==0:
                b_t=((0,k,0),)
            else:
                b_t=((0,j,-1),(j,k,0))
            black=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()


### FIXED CODE ###

def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    b=[[0]*(k+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":
            if int(y)%kk<k:
                b[int(x)%kk+1][int(y)%k+1]+=1
            else:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
        else:
            if int(y)%kk<k:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
            else:
                b[int(x)%kk+1][int(y)%k+1]+=1
    b=[list(ac(i)) for i in b]
    for i in range(1,kk+1):
        for j in range(k+1):
            b[i][j]+=b[i-1][j]
    ans=0
    for i in range(kk):
        if i==0:
            a_t=((i,i+k,0),(i+k,kk,1))
        elif i<k:
            a_t=((0,i,-1),(i,i+k,0),(i+k,kk,1))
        elif i==k:
            a_t=((0,i,-1),(i,kk,0))
        else:
            a_t=((0,i-k,-2),(i-k,i,-1),(i,kk,0))
        for j in range(k):
            if j==0:
                b_t=((0,k,0),)
            else:
                b_t=((0,j,-1),(j,k,0))
            black=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()
### BUGGY CODE ###

import math

K = int(input())

res = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            tmp = math.gcd(a, math.gcd(b,c))
            #print(tmp)
            res+=tmp


print(res)



### FIXED CODE ###

import math

K = int(input())

res = [math.gcd(a, math.gcd(b,c))  for a in range(1, K+1) for b in range(1, K+1) for c in range(1, K+1)]
 


print(sum(res))
### BUGGY CODE ###

w, h, n = map(int, input().split())

vec = []

l = []
b = []
r = []
t = []
for i in range(n):
    x, y, x1, y1 = map(int, input().split())
    if x == 0:
        l.append([x, y, i])
    elif y == 0:
        t.append([x, y, i])
    elif x == w:
        r.append([x, y, i])
    elif y == h:
        b.append([x, y, i])
    if x1 == 0:
        l.append([x1, y1, i])
    elif y1 == 0:
        t.append([x1, y1, i])
    elif x1 == w:
        r.append([x1, y1, i])
    elif y1 == h:
        b.append([x1, y1, i])

sorted_node = (
          sorted(l, key=lambda x: x[1])
        + sorted(b, key=lambda x: x[0])
        + sorted(r, key=lambda x: x[1], reverse=True)
        + sorted(t, key=lambda x: x[0], reverse=True)
        )

colors = list(map(lambda x: x[2], sorted_node))

colors = list(filter(lambda x:colors.count(x) % 2 == 0, set(colors)))

stack = []

for node in sorted_node:
    if node[2] in colors:
        if not stack or stack[-1] != node[2]:
            stack.append(node[2])
        else:
            stack.pop()

print("NO" if stack else "YES")



### FIXED CODE ###

w, h, n = map(int, input().split())

vec = []

l = []
b = []
r = []
t = []
for i in range(n):
    x, y, x1, y1 = map(int, input().split())
    c = [x, y, x1, y1]
    if( ((c[0] == 0 or c[0] == w) or (c[1] == 0 or c[1] == h)) and ((c[2] == 0 or c[2] == w) or (c[3] == 0 or c[3] == h)) ):
        if x == 0:
            l.append([x, y, i])
        elif y == 0:
            t.append([x, y, i])
        elif x == w:
            r.append([x, y, i])
        elif y == h:
            b.append([x, y, i])
        if x1 == 0:
            l.append([x1, y1, i])
        elif y1 == 0:
            t.append([x1, y1, i])
        elif x1 == w:
            r.append([x1, y1, i])
        elif y1 == h:
            b.append([x1, y1, i])

sorted_node = (
          sorted(l, key=lambda x: x[1])
        + sorted(b, key=lambda x: x[0])
        + sorted(r, key=lambda x: x[1], reverse=True)
        + sorted(t, key=lambda x: x[0], reverse=True)
        )


stack = []

for node in sorted_node:
    if not stack or stack[-1] != node[2]:
        stack.append(node[2])
    else:
        stack.pop()

print("NO" if stack else "YES")
### BUGGY CODE ###

N=int(input())
print(sum(range(1,N)))


### FIXED CODE ###

N=int(input())
print(sum(range(1,N)))
### BUGGY CODE ###

s = input().strip()
q = int(input().strip())
queries = [input().split() for _ in range(q)]
for que in queries:
    if que[0] == "1":
        s = s[::-1]
    elif que[0] == "2":
        if que[1] == "1":
            s = que[2] + s
        elif que[1] == "2":
            s += que[2]
print(s)


### FIXED CODE ###

s = list(input().strip())
q = int(input().strip())
queries = []
one_count = 0
one_counts = []
for i in range(q):
    inp = input().split()
    queries.append(inp)
    if inp[0] == "1":
        one_count += 1
    one_counts.append(one_count)
one_counts = list(map(lambda x: (one_count - x), one_counts))
if one_count % 2 == 1:
    s = s[::-1]
pre = []
suf = []
for i in range(q):
    if queries[i][0] == "1":
        continue
    elif queries[i][0] == "2":
        if queries[i][1] == "1":
            if one_counts[i] % 2 == 0:
                pre.append(queries[i][2])
            else:
                suf.append(queries[i][2])
        elif queries[i][1] == "2":
            if one_counts[i] % 2 == 0:
                suf.append(queries[i][2])
            else:
                pre.append(queries[i][2])
print("".join(pre[::-1] + s + suf))
### BUGGY CODE ###

from operator import itemgetter
n,m = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a,reverse = True)
x = []
for _ in range(m):
    b,c = map(int,input().split())
    x.append([c,b])
x.sort(key = itemgetter(0),reverse = True)
y = []
i=0
j=0
#print(a,x)
s=0
while len(y)<n:
    if (j == len(x)) or (a[i]>x[j][0]):
        y.append(a[i])
        s+=a[i]
        i+=1
    else:
        if len(y + [x[j][0]]*x[j][1]) > n:
            temp = n - len(y)
            y = y + [x[j][0]]*temp
            s = s + x[j][0]*temp
        else:
            y = y + [x[j][0]]*x[j][1]
            s = s + x[j][0]*x[j][1]
        #print(y)
        j+=1
y = y[:n]
print(s)

### FIXED CODE ###

from operator import itemgetter
n,m = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a,reverse = True)
x = []
for _ in range(m):
    b,c = map(int,input().split())
    x.append([c,b])
x.sort(key = itemgetter(0),reverse = True)
i=0
j=0
#print(a,x)
s=0
p = 0
x1 = len(x)
while p<n:
    if (j == x1) or (a[i]>x[j][0]):
        s+=a[i]
        p+=1
        i+=1
    else:
        if (p + x[j][1]) > n:
            temp = n - p
            p+=temp
            s = s + x[j][0]*temp
        else:
            p = p + x[j][1]
            s = s + x[j][0]*x[j][1]
        #print(y)
        j+=1
print(s)
### BUGGY CODE ###

#%%
s = list(input())
ans = 0
i = 0

while True:
    if i < 0 :
        i += 1
    elif len(s)-2 <= i:
        break
    else:
        if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
            ans += 1
            s[i], s[i+1], s[i+2] = 'B', 'C', 'A'
            i -= 1
        else:
            i += 1

print(ans)


### FIXED CODE ###

#%%
s = list(input())
i = 0
ss = ''

while True:
    if i <= len(s) - 2:
        if s[i] == 'B' and s[i+1] == 'C':
            ss += 'D'
            i += 2
        else:
            ss += s[i]
            i += 1          
    else:
        ss += s[i]
        i += 1
    if i >= len(s):
        break
#print(ss)

a = 0
ans = 0
for i in range(len(ss)):
    if ss[i] == 'A':
        a += 1
    elif ss[i] == 'D':
        ans += a
    else:
        a = 0
print(ans)

#%%
### BUGGY CODE ###

N= int(input())
inlis = list(map(int,input().split()))
donelis =[]
for i in inlis:
    donelis.append(i+1)
    donelis.append(i)
    donelis.append(i-1)
estc =0
for i in donelis:
    a =donelis.count(i)
    if estc < a:
        estc = a
print(estc)

### FIXED CODE ###

n = int(input())
inlis = list(map(int,input().split()))
donelis =[]
numlis=[]

for i in inlis:
    donelis.append(i+1)
    donelis.append(i)
    donelis.append(i-1)

estc =0
donelis.sort()
a = -2
count=0
for i in donelis:
    if a != i:
        if count > estc:
            estc = count
        count = 1
        a = i
    else:
        count +=1
if count >estc:
    estc =count
print(estc)
### BUGGY CODE ###

import sys
#input = sys.stdin.readline

def main():
    N = int(input())
    s = [list(map(str,input())) for _ in range(N)]
    s += s
    ans = 0
    for i in range(N):
        b = True
        for x in range(N):
            for y in range(N):
                if s[x+i][y] != s[y+i][x]:
                    b = False
        if b:
            ans += N
    
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#input = sys.stdin.readline
import numpy as np

def main():
    N = int(input())
    s = [list(map(str,input())) for _ in range(N)]
    s = np.array(s)
    ans = 0
    for i in range(N):
        T = np.vstack((s[i:],s[:i]))
        if np.all(T==T.T):
            ans += N
            
    print(ans)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
ws = [x[0] for x in wv]
vs = [x[1] for x in wv]

dp = [{} for _ in range(100)]
def dfs(weight=0, depth=N - 1):
    if dp[depth].get(weight) is not None:
        return dp[depth][weight]

    if depth == -1:
        return 0

    if weight + ws[depth] <= W:
        result = max(dfs(weight + ws[depth], depth - 1) + vs[depth], dfs(weight, depth - 1))
    else:
        result = dfs(weight, depth - 1)
    dp[depth][weight] = result
    return result

print(dfs())


### FIXED CODE ###

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
ws = [x[0] for x in wv]
vs = [x[1] for x in wv]

dp = [[None] * (10**5 + 1) for _ in range(100 + 1)]
# def dfs(weight=0, depth=N - 1):
#     if dp[depth][weight] is not None:
#         return dp[depth][weight]
#
#     if depth == -1:
#         dp[depth][weight] = 0
#         return 0
#
#     if weight + ws[depth] <= W:
#         result = max(dfs(weight, depth - 1), dfs(weight + ws[depth], depth - 1) + vs[depth])
#     else:
#         result = dfs(weight, depth - 1)
#     dp[depth][weight] = result
#     return result
#
# print(dfs())

dp[-1] = [0] * len(dp[-1])
for depth in range(0, N):
    for weight in range(10**5 + 1):
        v = dp[depth - 1][weight]
        if weight + ws[depth] <= W:
            dp[depth][weight] = max(v, dp[depth - 1][weight + ws[depth]] + vs[depth])
        else:
            dp[depth][weight] = v

print(dp[N - 1][0])
### BUGGY CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
lis = []
prv = -1
for i in range(n):
    if prv != A[i]:
        lis.append(A[i])
        prv = A[i]
#print(lis)
def dfs(money,kabu,now):
    global ans
    if now == len(lis):
        ans = max(money,ans)
        return;
    dfs(money + kabu*lis[now],0,now+1)
    dfs(money - lis[now] * (money//lis[now]),money//lis[now],now+1)
    dfs(money,kabu,now+1)
ans = 1000
dfs(1000,0,0)
print(ans)


### FIXED CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
money = 1000
kabu = 0
for i in range(1,n):
    if A[i-1] < A[i]:
        kabu = money // A[i-1]
        money -= kabu * A[i-1]
        money += kabu * A[i]
        kabu = 0
    #print(money,kabu)
print(money)
### BUGGY CODE ###

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

boxes=[0]*n #if ball in boxes[i-1]=boxes no.i
#b=[]
#m=len(b)
i=n #iの番号が書いた箱、インデックスはa[i-1]について
while i>=1:
	count=a[i-1]
	for j in range(i+1,n+1):
		if j%i==0:
			count+=boxes[j-1]
	boxes[i-1]=count%2
	i-=1
#print(boxes)

b=[]
for i in range(n):
	if boxes[i]==1:
		b.append(i+1)
print(len(b))
print(*b)

### FIXED CODE ###

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

boxes=[0]*n #if ball in boxes[i-1]=boxes no.i
'''
b=[]
#m=len(b)
i=n #iの番号が書いた箱、インデックスはa[i-1]について
while i>=1:
	count=a[i-1]
	for j in range(i+1,n+1):
		if j%i==0:
			count+=boxes[j-1]
	boxes[i-1]=count%2
	if boxes[i-1]:
		b.append(i)
	i-=1
#print(boxes)

print(len(b))
print(*b) #space区切り
'''
for i in reversed(range(n)):
	boxes[i]=(a[i]+sum(boxes[i::i+1]))%2

print(sum(boxes))
for i in range(n):
	if boxes[i]:
		print(i+1,end=" ")
### BUGGY CODE ###

n=int(input())
list1=list(map(int,input().split()))
ln=[list1[0]]
c=0
for i in list1:
    if min(ln)>=i:
        c+=1
    ln.append(i)
print(c)

### FIXED CODE ###

n=int(input())
list1=list(map(int,input().split()))
mi=list1[0]
c=0
for i in list1:
    if mi>=i:
        mi=i
        c+=1
print(c)
### BUGGY CODE ###

import copy
import collections

#Input
n = int(input())
l_a = list(map(int, input().split()))

#Process
for i in range(n):
    l_o = copy.copy(l_a)
    del l_o[i]
    l_c = list(collections.Counter(l_o).values())
    Ans = 0
    for j in range(len(l_c)):
        if(l_c[j] != 1):
            Ans += int((l_c[j] - 1) * l_c[j] / 2)
    print(Ans)

### FIXED CODE ###

import collections

#Input
n = int(input())
l_a = list(map(int, input().split()))

#Process
d_c = collections.Counter(l_a)
l_c = list(d_c.values())

#N個から選ぶ方法
o = 0
for i in range(len(l_c)):
    if(l_c[i] != 1):
        o += int((l_c[i] - 1) * l_c[i] / 2)

#Output
for i in range(n):
    print(o - d_c[l_a[i]] + 1)
### BUGGY CODE ###

import math

N, M = list(map(int, input().split()))
price = list(map(int, input().split()))
total = sum(price)
for i in range(M):
    max_index = price.index(max(price))
    discount = math.ceil(max(price) / 2)
    total -= discount
    price[max_index] -= discount
print(total)

### FIXED CODE ###

import heapq

N, M = list(map(int, input().split()))
price = list(map(lambda x: int(x) * (-1), input().split()))

heapq.heapify(price)

for i in range(M):
    max_price = -(heapq.heappop(price))
    new_price = max_price // 2
    heapq.heappush(price, -(max_price // 2))

print(-(sum(price)))
### BUGGY CODE ###

s = input()
n = len(s)

memo = [0] * 2019
memo[0] += 1

num = 0
ten = 1
for i in reversed(s):
    num += int(i) * ten
    memo[num%2019] += 1
    ten *= 10

ans = 0
for p in memo:
    ans += p*(p-1)//2

print(ans)

### FIXED CODE ###

s = input()
n = len(s)

memo = [0] * 2019
memo[0] += 1

num = 0
t = 1
for i in reversed(s):
    num += int(i) * t
    num %= 2019
    t *= 10
    t %= 2019
    memo[num] += 1

ans = 0
for p in memo:
    ans += p*(p-1)//2

print(ans)
### BUGGY CODE ###

# sys.stdin.readline()
import sys
input = sys.stdin.readline

N,K=map(int, input().split())
h=list(map(int, input().split()))
 
# dpの最小値を変更する関数
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
      
f_inf = float('inf')
dp = [f_inf]*N
dp[0]=0
#dp[1]=abs(h[1]-h[0])
 
#配るDP
for i in range(N-1):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j]=chmin(abs(h[i]-h[i+j])+dp[i],dp[i+j])
    
print(dp[-1])

### FIXED CODE ###

# sys.stdin.readline()
import sys
input = sys.stdin.readline

N,K=map(int, input().split())
h=list(map(int, input().split()))
import numpy as np 
      
f_inf = float('inf')
dp = [f_inf]*N
dp[0]=0
# hの配列を作る。
h = np.array(h)
 
#配るDP
for i in range(1,N):
    # start は負になることはない。
    start = max(0, i-K)
    # 行列として足し算できるのでforを使う必要がない。
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))
    
print(dp[-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n)]
c = []
for i in range(n-1, -1, -1):
    d = 0
    for j in range(n-1, i, -1):
        if (j+1)%(i+1) == 0:
            d += b[j]
    if d%2 != a[i]:
        b[i] = 1
        c.append(i+1)
    else:
        b[i] = 0
if c == []:
    print(0)
else:
    print(len(c))
    for i in range(len(c)):
        print(c[i], end=' ')
    print()


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n)]
c = []
for i in range(n-1, -1, -1):
    b[i] = sum(b[i::i+1])%2^a[i]
    if b[i] == 1:
        c.append(i+1)
if c == []:
    print(0)
else:
    print(len(c))
    for i in range(len(c)):
        print(c[i], end=' ')
    print()
### BUGGY CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
s = str(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))
#A, B, C = map(int, stdin.readline().rstrip().split())
#S = [list(map(int, stdin.readline().rstrip().split())) for _ in range(h)]#hの定義を忘れずに

ans = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]:
                if j-i!=k-j:
                    ans += 1

print(ans)


### FIXED CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
s = str(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))
#A, B, C = map(int, stdin.readline().rstrip().split())
#S = [list(map(int, stdin.readline().rstrip().split())) for _ in range(h)]#hの定義を忘れずに

rnum = s.count("R")
gnum = s.count("G")
bnum = s.count("B")

ans = rnum * gnum * bnum

for i in range(n-2):
    for j in range(i+1,n-1):
        k = 2*j - i
        if k<n:
            if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k]:
                ans -= 1

print(ans)
### BUGGY CODE ###

n = int(input())
*p, = map(int,input().split())

ans = 0
for i in range(n-1):
    for j in range(n)[i+1:]:
        ans += sorted(p[i:j+1])[-2]

print(ans)

### FIXED CODE ###

N = int(input())
*p, = map(int, input().split())

LL = [0] + [i for i in range(N+1)]
RR = [i+1 for i in range(N+1)] + [N+1]

E = [(v,i+1) for i,v in enumerate(p)]
E.sort()

ans = 0
for v,i in E:
  r0 = RR[i]; r1 = RR[r0]
  l0 = LL[i]; l1 = LL[l0]
  RR[l0] = r0; LL[r0] = l0
  
  ans += ((r1 - r0)*(i-l0)+(r0-i)*(l0 - l1))*v

print(ans)
### BUGGY CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist.append(W[i])

#処理内容
def main():
	#入力
	N = int(input())
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#DFS
	W = [1] * N
	Wlist = []
	visit = ["No"] * N
	visit[0] = "Yes"
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist.append(N - W[i])

	# print(Wlist)
	pow2 = pow(2, N - 1, con)
	ans_up = N * (pow2 - 1)
	for i in Wlist:
		ans_up -= pow(2, i, con) - 1
		ans_up %= con

	# print(ans_up)

	ans = ans_up * pow(pow2 * 2, con - 2, con)
	print(ans % con)

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] == 0:
			visit[i] = 1
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist.append(W[i])

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque(); self.Q.append(s)
		self.dist = [INF] * N; self.dist[s] = 0
		self.prev = [None] * N; self.prev[s] = -1
		self.order = []
		while self.Q:
			v = self.Q.popleft()
			self.order.append(v)
			for i in self.g[v]:
				if self.dist[i] == INF:
					self.dist[i] = self.dist[v] + 1
					self.prev[i] = v
					self.Q.append(i)


#処理内容
def main():
	#入力
	N = int(input())
	G = Graph()
	Nedge = [0] * N
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)
		Nedge[a] += 1; Nedge[b] += 1

	W = [1] * N
	#葉の場合の処理
	# for i in range(N):
	# 	if Nedge[i] == 1:
	# 		W[i] = 1

	BF = BFS(G, 0, N)

	for i in range(N - 1, 0, -1):
		v = BF.order[i]
		W[BF.prev[v]] += W[v]

	Wlist = []
	for i in range(N):
		for j in G.graph[i]:
			if j != BF.prev[i]:
				Wlist.append(W[j])
	for i in range(N):
		Wlist.append(N - W[i])

	pow2 = pow(2, N - 1, con)
	ans_up = N * (pow2 - 1)
	for i in Wlist:
		ans_up -= pow(2, i, con) - 1
		ans_up %= con

	ans = ans_up * pow(pow2 * 2, con - 2, con)
	print(ans % con)

if __name__ == '__main__':
	main()