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

C = -(10**9 + 7)


def main():
    from collections import defaultdict
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = defaultdict(lambda: C)
    for i in range(N+1):
        dp[(i, 0)] = 0
        if i != 0:
            dp[(i, 1)] = max(dp[(i-1, 1)], A[i-1])
    for i in range(2, N+1):
        for j in range(max(i//2 - 1, 0), i+1//2 + 1):
            dp[(i, j)] = max(dp[(i, j)], dp[(i-1, j)],
                             dp[(i-2, j-1)] + A[i-1],
                             dp[(i-3, j-1)] + A[i-1])
    print(dp[(N, K)])
    # print(*dp, sep="\n")


if __name__ == '__main__':
    main()


### FIXED CODE ###

C = -(10**15 + 7)


def main():
    from collections import defaultdict
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = defaultdict(lambda: C)
    for i in range(N+1):
        dp[i, 0] = 0
        if i != 0:
            dp[(i, 1)] = max(dp[i-1, 1], A[i-1])
    for i in range(2, N+1):
        for j in range(i//2-1, (i+1)//2 + 1):
            if j < 0:
                continue
            # A_i(1-index)でj個選ばなければいけない
            dp[i, j] = max(dp[i, j], dp[i-2, j-1] + A[i-1],
                           dp[i-3, j-1] + A[i-1], dp[i-4, j-1] + A[i-1])
    print(max(dp[N, K], dp[N-1, K], dp[N-2, K]))
    # for i in range(N+1):
    #     for j in range(K+1):
    #         print("{:>4}".format(dp[i, j] if dp[i, j] != C else "C"),
    #               end=" " if j != K else "\n")


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

import itertools
import math

K = int(input())
nums = [i for i in range(1, K+1)]
product = itertools.product(nums, repeat=3)
ans = 0
for comb in product:
    m = min(comb)
    for i in range(3):
        m = math.gcd(m, comb[i])
    ans += m
print(ans)

### FIXED CODE ###

import itertools
import math

K = int(input())
nums = [i for i in range(1, K+1)]
product = itertools.product(nums, repeat=3)
ans = 0
for comb in product:
    m = min(comb)
    if m == 1:
        ans += m
    else:
        for i in range(0, 3):
            m = math.gcd(m, comb[i])
        ans += m
print(ans)
### BUGGY CODE ###

from sys import stdin

H, W = [int(x) for x in stdin.readline().rstrip().split()]
A = [stdin.readline().rstrip() for _ in range(H)]
B = [[A[y][x] for x in range(W)] for y in range(H)]
queue = []

for k in range(H):
    for l in range(W):
        if A[k][l] == '#':
            queue.append((k, l, 0))

while len(queue) > 0:
    h, w, t = queue.pop(0)
    if h > 0:
        if B[h - 1][w] == '.':
            B[h - 1][w] = '#'
            queue.append((h - 1, w, t + 1))
    if h < H - 1:
        if B[h + 1][w] == '.':
            B[h + 1][w] = '#'
            queue.append((h + 1, w, t + 1))
    if w > 0:
        if B[h][w - 1] == '.':
            B[h][w - 1] = '#'
            queue.append((h, w - 1, t + 1))
    if w < W - 1:
        if B[h][w + 1] == '.':
            B[h][w + 1] = '#'
            queue.append((h, w + 1, t + 1))
    if len(queue) == 0:
        print(t)



### FIXED CODE ###

from sys import stdin
from collections import deque

H, W = [int(x) for x in stdin.readline().rstrip().split()]
B = [list(stdin.readline().rstrip()) for _ in range(H)]

q = deque([])

for k in range(H):
    for l in range(W):
        if B[k][l] == '#':
            q.append((k, l, 0))

while len(q) > 0:
    h, w, t = q.popleft()
    if h > 0:
        if B[h - 1][w] == '.':
            B[h - 1][w] = '#'
            q.append((h - 1, w, t + 1))
    if h < H - 1:
        if B[h + 1][w] == '.':
            B[h + 1][w] = '#'
            q.append((h + 1, w, t + 1))
    if w > 0:
        if B[h][w - 1] == '.':
            B[h][w - 1] = '#'
            q.append((h, w - 1, t + 1))
    if w < W - 1:
        if B[h][w + 1] == '.':
            B[h][w + 1] = '#'
            q.append((h, w + 1, t + 1))
    if len(q) == 0:
        print(t)
### BUGGY CODE ###

def isprime(n):
    if n < 2: return 0
    elif n == 2: return 1

    if n % 2 == 0: return 0

    for i in range(3, n, 2):
        if n % i == 0 : return 0

    return 1

N = int(input())
n = [isprime(int(input())) for i in range(N)].count(1)

print(n)


### FIXED CODE ###

def isprime(n):
    if n < 2: return 0
    elif n == 2: return 1

    if n % 2 == 0: return 0

    for i in range(3, n, 2):
        if i > n/i: return 1
        if n % i == 0 : return 0

    return 1

N = int(input())
n = [int(input()) for i in range(N)]

a = [i for i in n if isprime(i)]

print(len(a))
### BUGGY CODE ###

x = int(input())

s = 10000
for i in range(-s, s):
    flag = False
    for j in range(-s, s):
        tmp = i ** 5 - j ** 5
        if tmp == x:
            print('{} {}'.format(i, j))
            flag = True
            break
    if flag:
        break



### FIXED CODE ###

x = int(input())

for i in range(-1000, 1000):
    flag = False
    for j in range(-1000, 1000):
        tmp = i ** 5 - j ** 5
        if tmp == x:
            print('{} {}'.format(i, j))
            flag = True
            break
    if flag:
        break
### BUGGY CODE ###

na,nb,k = map(int, input().split())
ta = list(map(int, input().split()))
tb = list(map(int, input().split()))
 
def get_bcnt( usek,tb=tb ):
    t = 0
    cnt = 0
    try:
        while True:
            if t + tb[cnt] > usek:
                return cnt
            else:
                t += tb[cnt]
                cnt += 1
    except:
        return len(tb)
 
sumta = 0
readbook = [get_bcnt(k)] 
for i in range(na):
    sumta += ta[i]
    if sumta > k:
        break
    if ta[i] <= k:
        readbook.append( i+1 + get_bcnt( k - sumta ) )
 
print( max(readbook) )

### FIXED CODE ###

na,nb,k = map(int, input().split())
ta = list(map(int, input().split()))
tb = list(map(int, input().split()))

a = [0]
for i in range(na):
  a.append( a[i] + ta[i] )
b = [0]
for i in range(nb):
  b.append( b[i] + tb[i] )

ans, j=0, nb
for i in range(na + 1):
  if a[i] > k:
    break
  while True:
    if a[i] + b[j] > k:
      j -= 1
    else:
      break
  ans = max(ans, i+j)
    
print(ans)
### BUGGY CODE ###

n = int(input())
list = list(range(9, 1, -1))
ans = 0
flag = 1

if n > 1:
    while n > 1:
        for i in list:
            if n % i == 0:
                n = n / i
                ans += 1
                flag = 0
                break

        if flag == 1:
            ans = 0
            break
elif n == 1:
    ans = 2

if 0 < ans <= 2:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

n = int(input())
list = list(range(9, 1, -1))
ans = 0

if n > 1:
    while n > 1:
        flag = 1
        for i in list:
            if n % i == 0:
                n = n / i
                ans += 1
                flag = 0
                break

        if flag == 1:
            ans = 0
            break
elif n == 1:
    ans = 2

if 0 < ans <= 2:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n = int(input())
string = input()
rs = [0]
gs = [0]
bs = [0]
for idx, c in enumerate(string):
    add = [0]*3
    if c == 'R':
        add[0] += 1
    elif c == 'G':
        add[1] += 1
    else:
        add[2] += 1
    for l, s in zip((rs, gs, bs), add):
        l.append(l[idx]+s)

d = {'R':rs, 'G': gs, 'B': bs}
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if string[i] == string[j]: 
            continue
        rgb = set(['R', 'G', 'B'])
        rgb.remove(string[i])
        rgb.remove(string[j])
        k = rgb.pop()
        cumsum = d[k]
        ans += cumsum[-1] - cumsum[j+1]
        if 2*j-i < n and string[2*j-i] == k:
            ans -= 1

print(ans)
        
        


### FIXED CODE ###

n = int(input())
string = input()
r = 0
g = 0
b = 0
for c in string:
    if c == 'R':
        r += 1
    elif c == 'G':
        g += 1
    else:
        b += 1
ans = r*g*b
for i in range(n):
    for j in range(i+1, n):
        if 2*j - i >= n:
            break
        
        if string[i] != string[j] and string[i] != string[2*j-i] and string[j] != string[2*j-i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())
Alist=list(map(int, input().split()))
numdic = {}
for i in Alist:
    if i in numdic:
        numdic[i] += 1
    else:
        numdic[i] = 1
ansdic = dict.fromkeys(numdic, [0,False])
for i in Alist:
    if ansdic[i][1]:
        print(ansdic[i][0])
    else:
        kazu = 0
        numdic[i] -= 1
        for l in numdic.values():
            kazu += l*(l-1)//2
        ansdic[i] = [kazu,True]    
        numdic[i] += 1
        print(kazu)

### FIXED CODE ###

N = int(input())
Alist=list(map(int, input().split()))
numdic = {}
for i in Alist:
    if i in numdic:
        numdic[i] += 1
    else:
        numdic[i] = 1
Apple = 0
for i in numdic.values():
    Apple += i*(i-1)//2
for i in Alist:
    tmp = Apple
    tmp -= (numdic[i]-1)
    print(tmp)
### BUGGY CODE ###

a=list(map(int,input().split()))
b=[]
c=[1]*(a[0]-1)
for i in range(a[1]):
  b.append(list(map(int,input().split())))
b=sorted(b,key=lambda b:b[1])
for i in range(a[1]):
  if i!=0 and b[i-1][0]>=b[i][0]:
    continue
  if 0 in c[(b[i][0]-1):b[i][1]]:
    continue
  else:
    c[(b[i][1])-2]=0

print(c.count(0))

### FIXED CODE ###

a=list(map(int,input().split()))
b=[]
c=0
r=0
for i in range(a[1]):
  b.append(list(map(int,input().split())))
b=sorted(b,key=lambda b:b[1])

for i in range(a[1]):
  if b[i][0]<=r:
    continue
  else:
    c=c+1
    r=b[i][1]-1

print(c)
### BUGGY CODE ###

n = int(input())
a = list(int(input()) for i in range(n))
kami = []

for i in a :
    if i in kami :
        kami.remove(i)
    else :
        kami.append(i)

print(len(kami))


### FIXED CODE ###

n = int(input())
kami = set()

for i in range(n) :
    a = int(input())
    if a in kami :
        kami.remove(a)
    else :
        kami.add(a)

print(len(kami))
### BUGGY CODE ###

import heapq

def main():
    q = []
    heapq.heapify(q)
    while True:
        s = input().split()
        if s[0] == 'end':
            break
        elif s[0] == 'insert':
            heapq.heappush(q, (-int(s[1]), int(s[1])))
        else:
            p = heapq.heappop(q)
            print(p[1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import heapq

def main():
    q = []
    heapq.heapify(q)
    while True:
        s = input().split()
        if s[0] == 'end':
            break
        elif s[0] == 'insert':
            heapq.heappush(q, -int(s[1]))
        else:
            p = heapq.heappop(q)
            print(-p)

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

#import
#import math
import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

x = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, W + 1):
        dp[i][j] = dp[i - 1][j]
        if x[i - 1][0] <= j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-x[i-1][0]] + x[i-1][1])

print(dp[-1][W])


### FIXED CODE ###

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

x = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, W + 1):
        dp[i][j] = dp[i - 1][j]
        if i != 0 and x[i - 1][0] <= j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-x[i-1][0]] + x[i-1][1])

print(dp[-1][W])
### BUGGY CODE ###

n = raw_input()
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b,a%b)



def f(ais):
	seen = set()
	bis = ais[::]
	flag=  True
	for ai in bis[::]:
		factor =2
		while(ai != 1):
			if ai % factor == 0:
				if factor in seen:
					flag = False
					break
				while(ai % factor == 0):
					ai /= factor

				seen.add(factor)
			factor +=1
	if flag:
		return 'pairwise coprime'
	if reduce(gcd, ais) == 1:
		return 'setwise coprime'
	return 'not coprime'
print f(map(int, raw_input().split()))

### FIXED CODE ###

n = raw_input()
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b,a%b)

def g(ais): return reduce(gcd, ais) == 1

def f(ais):
	seen = set()
	for ai in ais:
		factor =2
		oi = ai
		while(ai != 1 and factor * factor <= oi):
			if ai % factor == 0:
				if factor in seen:
					return False
				while(ai % factor == 0):
					ai /= factor
				seen.add(factor)
			factor +=1
		if ai != 1:
			if ai in seen: return False
			seen.add(ai) 
	return True

ais = map(int, raw_input().split())

if f(ais):
	print 'pairwise coprime'
elif g(ais):
	print 'setwise coprime'
else:
	print 'not coprime'
### BUGGY CODE ###

import math
k = int(input())

ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans = ans + math.gcd(a,math.gcd(b,c))

print(ans)


### FIXED CODE ###

import math
k = int(input())

ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    tmp = math.gcd(a,b)
    for c in range(1,k+1):
      ans += math.gcd(c,tmp)

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

X,Y,Z,K = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ab = []
for ai in a:
    for bj in b:
        ab.append(ai+bj)
ab.sort(reverse=True)
ab = ab[:K]
cond = []
for abi in ab:
    for cj in c:
        cond.append(abi+cj)
cond = sorted(cond, reverse=True)[:K]
for condi in cond:
    print(condi)


### FIXED CODE ###

import sys
readline = sys.stdin.readline
X,Y,Z,K = map(int, readline().split())
a = sorted(list(map(int, readline().split())), reverse=True)
b = sorted(list(map(int, readline().split())), reverse=True)
c = sorted(list(map(int, readline().split())), reverse=True)

ab = []
for ai in a:
    for bj in b:
        ab.append(ai+bj)
ab.sort(reverse=True)
ab = ab[:K]
cond = []
for abi in ab:
    for cj in c:
        cond.append(abi+cj)
cond = sorted(cond, reverse=True)[:K]
for condi in cond:
    print(condi)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
game = [0]

for _ in range(n):
    comp = list(map(int, input().split()))[::-1]
    game.append(comp)

count = 0
final = n*(n-1)//2
for day in range(1, 1000000):
    finish = set()
    possible = False
    for me in range(1, n+1):
        if me in finish or game[me] == []:
            continue

        you = game[me][-1]
        if you in finish or game[you] == []:
            continue
        else:
            if game[you][-1] == me:
                finish.add(game[you].pop())
                finish.add(game[me].pop())
                possible = True
                count += 1
            else:
                continue

    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
game = {}

for i in range(1, n+1):
    game[i] = deque((map(int, input().split())))

count = 0
final = n*(n-1)//2
done = []

finish = [0] * (n + 1)
for me in range(1, n + 1):
    if finish[me] == 1 or game[me] == deque([]):
        continue

    you = game[me][0]
    if finish[you] == 1:
        continue
    else:
        if game[you][0] == me:
            done.append(you)
            done.append(me)
            finish[game[you].popleft()] = 1
            finish[game[me].popleft()] = 1
            possible = True
            count += 1
        else:
            continue

for day in range(2, 1000000):
    finish = [0]*(n+1)
    possible = False
    new_done = []
    for me in done:
        if finish[me] == 1 or game[me] == deque([]):
            continue

        you = game[me][0]
        if finish[you] == 1:
            continue
        else:
            if game[you][0] == me:
                finish[game[you].popleft()] = 1
                finish[game[me].popleft()] = 1
                new_done.append(me)
                new_done.append(you)
                possible = True
                count += 1
            else:
                continue
    done = new_done
    if not possible:
        print(-1)
        exit()

    if count == final:
        print(day)
        exit()
### BUGGY CODE ###

from sys import stdin
from math import factorial
from itertools import combinations

n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()
s = [int(i) for i in s]

lin = list(combinations(s, 3))

lin = list(set(lin))

print(len(lin))

### FIXED CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()

def count(poi):
    point = 0
    for i in range(poi):
        bango = str(i).zfill(3)
        count = 0
        for j in range(n):
            if s[j] == bango[count]:
                count += 1
            if count == 3:
                point += 1
                break
    return point

print(count(1000))
### BUGGY CODE ###

mod = 998244353
N,M,K = map(int,input().split())
ans = 0
def pow(x,n):
    if n == 0:  
        return 1
    if n % 2 == 0:  
        return pow((x ** 2)%mod, n // 2)%mod
    else:
        return x * pow((x ** 2)%mod, (n - 1) // 2)%mod
A = 1
for i in range(K+1):
    p = N - i
    x = M*pow(M-1,p-1)*A % mod
    ans += x
    A = A*(N-i-1)%mod
    y = pow(i+1,mod-2)
    A = A*y % mod
print(ans%mod)

### FIXED CODE ###

mod = 998244353
N,M,K = map(int,input().split())
ans = 0
def pow(x,n):
    if n == 0:  
        return 1
    if n % 2 == 0:  
        return pow((x ** 2)%mod, n // 2)%mod
    else:
        return x * pow((x ** 2)%mod, (n - 1) // 2)%mod
A = 1
for i in range(K+1):
    p = N - i
    x = M*pow(M-1,p-1)*A % mod
    ans += x
    A = A*(N-i-1)%mod
    y = pow(i+1,mod-2)
    A = A*y % mod
print(ans%mod)
### BUGGY CODE ###

n = int(input())
divisors = []
for i in range(1, int(pow(n, 0.5)) + 1):
    if n % i == 0:
        divisors.append([i, n // i])
    divisors = sorted(divisors, key= lambda x:x[1])
res = 0
for i in divisors[0]:
    res += i - 1

print(res)

### FIXED CODE ###

import math

n = int(input())
divisors = []
for i in range(1, int(n**0.5) +1):
    if n % i == 0:
        divisors.append(i)
        if i != n // i:
            divisors.append(n//i)

ans = math.pow(10, 12)
tmp = 0
for i in divisors:
    j = n / i
    tmp = i + j -2
    if tmp < ans:
        ans = tmp

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

from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

def check(t):
    "if the number of the pairs (i, j) that satisfies Ai * Aj <= t is < K, return True"
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            index = bisect_right(As, t//A, lo = i+1) - (i+1)
        elif A < 0:
            index = N - bisect_left(As, -(t//(-A)), lo = i+1)
        else:
            if t < 0:
                index = 0
            else:
                index = N - i - 1
        count += index
        if count >= K:
            return False
    return (count < K)
        

l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while r - l > 1:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid

print(r)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)
### BUGGY CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
  print(collections.Counter(a)[i])

### FIXED CODE ###

import collections
n=int(input())
c=collections.Counter(list(map(int,input().split())))
for i in range(1,n+1):
  print(c[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
abc = [[int(j) for j in input().split()] for _ in range(N-1)]
Q,K = map(int, input().split())
xy = [ [int(j) for j in input().split()] for _ in range(Q)]

inf = float("inf")
con = [ [] for _ in range(N+1)]
cost = [ [inf] * (N+1) for _ in range(N+1)]

for i in range(N-1):
    a,b,c = abc[i]
    con[a].append(b)
    con[b].append(a)
    cost[a][b] = c
    cost[b][a] = c

def dfs(a,b, par):
    if cost[a][b] != inf :
        return cost[a][b]
    # if cost[b][a] != inf:
    #     return cost[b][a]

    if len(list(filter(lambda x: x!=par, con[a]))) == 0:
        cost[a][b] = inf
        cost[b][a] = inf
        return inf

    cst = inf
    idx= -1
    for e,ch in enumerate(con[a]):
        if ch == par:
            continue
        if cst > cost[a][ch] + dfs(ch,b,a):
            cst = cost[a][ch] + dfs(ch,b,a)
            idx = e
    if idx != -1:
        mn = min(cst, cost[a][b] , cost[b][a])
        cost[a][b] = mn
        # cost[b][a] = mn
    return cst

for i in range(Q):
    x,y = xy[i]
    print(dfs(x,K,None) + dfs(K,y,None))
    


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
abc = [[int(j) for j in input().split()] for _ in range(N-1)]
Q,K = map(int, input().split())
xy = [ [int(j) for j in input().split()] for _ in range(Q)]

inf = float("inf")
con = [ [] for _ in range(N+1)]
# cost = [ [inf] * (N+1) for _ in range(N+1)]
# cost = {}
from collections import defaultdict
# cost =  defaultdict(  )

for i in range(N-1):
    a,b,c = abc[i]
    con[a].append((b, c))
    con[b].append((a, c))

q = [(K,0)]
visited = [False] * (N+1)
visited[K] = True
costmap = [inf] * (N+1)
costmap[K] = 0
while q:
    n,cst = q.pop()
    for ch,chcst in con[n]:
        if visited[ch]:
            continue
        q.append( (ch, cst+chcst))
        visited[ch] = True
        costmap[ch]  = cst+ chcst
    
# def dfs(a,b, par):
#     if cost[a][b] != inf :
#         return cost[a][b]
# 
#     if len(list(filter(lambda x: x!=par, con[a]))) == 0:
#         return inf
# 
#     cst = inf
#     idx= -1
#     for e,ch in enumerate(con[a]):
#         if ch == par:
#             continue
#         if cst > cost[a][ch] + dfs(ch,b,a):
#             cst = cost[a][ch] + dfs(ch,b,a)
#             
#             idx = e
#     if idx != -1:
#         cost[a][b] = cst
#         cost[b][a] = cst
#     return cst
# 
for i in range(Q):
    x,y = xy[i]
    print( costmap[x] + costmap[y])
# for i in range(Q):
#     x,y = xy[i]
#     # _ = dfs(K,x,None)
#     # _ = dfs(y,K, None)
#     print(dfs(x,K,None) + dfs(K,y,None))
### BUGGY CODE ###

# python3
# -*- coding: utf-8 -*-
import sys
import math
import bisect
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint

INF = float('inf')

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
lmtx = lambda h: [list(map(int, lmis())) for _ in range(h)]
sys.setrecursionlimit(1000000000)


def lcm(a, b):
    return (a * b) // gcd(a, b)


# main
n = ii()
alist = lmis()

sum = 0
for i in range(n-1):
    for j in range(i+1, n):
        sum += alist[i] * alist[j]

print(sum % 1000000007)


### FIXED CODE ###

# python3
# -*- coding: utf-8 -*-
import sys
import math
import bisect
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint

INF = float('inf')

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
lmtx = lambda h: [list(map(int, lmis())) for _ in range(h)]
sys.setrecursionlimit(1000000000)


def lcm(a, b):
    return (a * b) // gcd(a, b)


# main
n = ii()
alist = lmis()

asum = sum(alist[1:n])

sum = 0
for i in range(n-1):
    sum += alist[i] * asum
    asum -= alist[i+1]

print(sum % 1000000007)