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

# coding: utf-8
import sys
from fractions import gcd
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()

@lru_cache(None)
def solve(index, n, g):
    '''既に１つ数を選んだらnは１'''
    if index == N:
        return g
    if n == 1:
        return solve(index+1, 1, gcd(g, A[index]))
    else:
        ret = max(solve(index+1, 1, g), solve(index+1, 0, gcd(g, A[index])))
        return ret

result1 = solve(0, 0,  A[0])
result2 = solve(0, 0, A[-1])
answer = max(result1, result2)
print(answer)


### FIXED CODE ###

from fractions import gcd
import math
N = int(input())
A = list(map(int, input().split()))

gl = [0] * (N-1)
gr = [0] * (N-1)

gl[0] = A[0]
gr[0] = A[-1]
for i in range(1,N-1):
    gl[i] = gcd(gl[i-1],A[i])
    gr[i] = gcd(gr[i-1],A[-i-1])
#print(gl[i])
ans = max(gr[-1],gl[N-2])
for i in range(1,N-1):
    g = gcd(gl[i-1],gr[-i-1])
    ans = max(ans,g)
#print(gl,gr)
print(ans)
### BUGGY CODE ###

# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy


N,M=map(int, input().split())
A = np.array(list(map(int, input().split())))

for _ in range(M):
    B,C=map(int, input().split())
    for _ in range(B):
        minA = min(A)
        idx = np.argmin(A)
        if minA < C:
            A[idx] = C

print(sum(A))

### FIXED CODE ###

# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy
from time import time

N,M=map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
update = []

for _ in range(M):
    temp = list(map(int, input().split()))
    update.append(temp)

# C_i の値をkeyにしてソートする
update = sorted(update,key = lambda x:x[1], reverse=True)

idx = 0
for b, c in update:
    for i in range(b):
        if idx >= N:
            break
        if A[idx] < c:
            A[idx] = c
            idx += 1
        else:
            break

print(sum(A))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections
import time

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        b = False
        for i,q in enumerate(Q):
            if gamed[i] > 0 or len(q) == 0:
                continue
            j = q[0] - 1
            if gamed[j] > 0 or len(Q[j]) == 0:
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                q.popleft()
                Q[j].popleft()
                gamed[i] = 1
                gamed[j] = 1
                games -= 1
                b = True
        days += 1
        if not b:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

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

from math import ceil
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

K = int(input())
L = list(map(int, input().split()))

maxr = 2
minr = 2
r = 0
for n in reversed(L):
    if any(x % n == 0 for x in range(minr, maxr+1)):
        # if minr//n <= maxr//n:
        minr = ceil(minr/n)*n
        maxr = (maxr)//n*n+n-1
    else:
        n = -1
        break

if n == -1:
    print(n)
else:
    print(int(minr), maxr)


### FIXED CODE ###

from math import ceil
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

K = int(input())
L = list(map(int, input().split()))

maxr = 2
minr = 2
r = 0
for n in reversed(L):
    #print("max={}min={}".format(maxr, minr))
    if ceil(maxr//n)*n >= minr:
        # if any(x % n == 0 for x in range(minr, maxr+1)):
        # if minr//n <= maxr//n:
        minr = ceil(minr/n)*n
        maxr = (maxr)//n*n+n-1
    else:
        n = -1
        break

if n == -1:
    print(n)
else:
    print(int(minr), maxr)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
dp = [[0] * (N+1) for _ in range(N+1)]

for width in range(1, N+1):
    for i in range(N-width+1):
        j = i + width

        if (N - width) % 2 == 0:
            dp[i][j] = max(dp[i+1][j] + A[i], dp[i][j-1] + A[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - A[i], dp[i][j-1] - A[j-1])

print(dp[0][N])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
dp = [[0] * (N+1) for _ in range(N+1)]

for width in range(1, N+1):
    for i in range(N-width+1):
        j = i + width

        if (N - width) % 2 == 0:
            dp[i][j] = max(dp[i+1][j] + A[i], dp[i][j-1] + A[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - A[i], dp[i][j-1] - A[j-1])

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

from itertools import accumulate

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

s = 0
for j in range(n):
    s += list(accumulate(a[j:])).count(0)

print(s)

### FIXED CODE ###

from itertools import accumulate
from collections import Counter


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

l = [0] + list(accumulate(a))
c = Counter(l)


s = 0
for key, value in c.items():
    s = s + value * (value - 1) // 2

print(s)
### BUGGY CODE ###

N, M = map(int,input().split())
List_A = list(map(int,input().split()))
List_BC = [list(map(int,input().split())) for i in range(M)]

List_A.sort()
List_BC.sort(key=lambda x:x[1], reverse=True)
flag = 0

for i in range(M):
    for j in range(List_BC[i][0]):
        if List_BC[i][1] > List_A[0]:
            List_A[0] = List_BC[i][1]
            List_A.sort()
        else:
            flag = 1
            break
    if flag == 1:
        break

tmp = 0
for i in range(N):
    tmp += List_A[i]
    
print("{}".format(tmp))

### FIXED CODE ###

N, M = map(int,input().split())
List_A = list(map(int,input().split()))
List_BC = [list(map(int,input().split())) for i in range(M)]

List_A.sort()
List_BC.sort(key=lambda x:x[1], reverse=True)
flag = 0
k = 0

for i in range(M):
    for j in range(List_BC[i][0]):
        if k >= N:
            flag = 1
            break
        elif List_BC[i][1] > List_A[k]:
            List_A[k] = List_BC[i][1]
            k += 1
        else:
            flag = 1
            break
    if flag == 1:
        break

tmp = 0
for i in range(N):
    tmp += List_A[i]
    
print("{}".format(tmp))
### BUGGY CODE ###

import math
k = int(input())
s = 0
for a in range(1, k+1):
  for b in range(1, k+1):
    for c in range(1, k+1):
      s += math.gcd(math.gcd(a, b), c)

print(s)

### FIXED CODE ###

import math
k = int(input())
s = 0
for a in range(1, k+1):
  for b in range(1, k+1):
    for c in range(1, k+1):
      s += math.gcd(math.gcd(a, b), c)

print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from itertools import product
INF = 10**18

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    XYP.sort(key=lambda xyp: max(abs(xyp[0]), abs(xyp[1])) * xyp[2], reverse=False)

    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = [INF] * (N + 1)
    for state in product((0, 1, 2), repeat=N):
        stateX = 0
        stateY = 0
        M = N
        for s in state:
            stateX <<= 1
            stateY <<= 1
            if s == 0: M -= 1
            if s == 1: stateX |= 1
            if s == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
            if cost >= ans[M]:
                break
        else:
            ans[M] = cost

    print(*ans, sep='\n')

sol()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
lrs = []
tbs = []

for y in range(h):
    left = 0
    while left < w:
        if ls[y][left] == '#':
            left += 1
            continue
        right = left
        while right < w:
            right += 1
            if right == w or ls[y][right] == '#':
                lrs.append([y, left, right, right - left])
                break
        left = right

for x in range(w):
    top = 0
    while top < h:
        if ls[top][x] == '#':
            top += 1
            continue
        bottom = top
        while bottom < h:
            bottom += 1
            if bottom == h or ls[bottom][x] == '#':
                tbs.append([x, top, bottom, bottom - top])
                break
        top = bottom
lrs.sort(key=lambda x: x[3], reverse=True)
tbs.sort(key=lambda x: x[3], reverse=True)

res = 0
for y, left, right, lh in lrs:
    for x, top, bottom, lv in tbs:
        if lh + lv - 1 <= res:
            break
        if top <= y <= bottom and left <= x <= right:
            res = max(res, lh + lv - 1)
            break
print(res)

### FIXED CODE ###

h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
counts = [[[-1] * w for _ in range(h)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        if ls[y][x] == '#':
            counts[0][y][x] = 0
        else:
            if x == 0:
                counts[0][y][x] = 1
            else:
                counts[0][y][x] = counts[0][y][x - 1] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[1][yy][xx] = 0
        else:
            if x == 0:
                counts[1][yy][xx] = 1
            else:
                counts[1][yy][xx] = counts[1][yy][xx + 1] + 1

        if ls[y][x] == '#':
            counts[2][y][x] = 0
        else:
            if y == 0:
                counts[2][y][x] = 1
            else:
                counts[2][y][x] = counts[2][y - 1][x] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[3][yy][xx] = 0
        else:
            if y == 0:
                counts[3][yy][xx] = 1
            else:
                counts[3][yy][xx] = counts[3][yy + 1][xx] + 1

res = 0
for y in range(h):
    for x in range(w):
        val = -3
        for i in range(4):
            val += counts[i][y][x]
        res = max(res, val)

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

from math import ceil


N, K = map(int, input().split())
A = list(map(int, input().split()))

divs = []
maxA = sum(A)
for i in range(maxA, ceil(maxA ** 0.5) - 1, -1):
    if maxA % i == 0:
        divs.append(i)
        divs.append(maxA // i)

divs.sort(reverse=True)

for d in divs:
    rest = [a % d for a in A]
    rest.sort(reverse=True)
    restSum = sum(rest) // d
    cnt = 0
    for i in range(restSum):
        cnt += d - rest[i]
    if cnt <= K:
        print(d)
        exit()


### FIXED CODE ###

from heapq import heappush, heappop


N, K = map(int, input().split())
A = list(map(int, input().split()))

divs = []
maxA = sum(A)
for i in range(1, int(maxA ** 0.5) + 1):
    if maxA % i == 0:
        heappush(divs, -i)
        j = maxA // i
        if i != j:
            heappush(divs, -j)

while True:
    d = -heappop(divs)
    q = []
    asum = 0
    for a in A:
        rest = a % d
        asum += rest
        heappush(q, -rest)
    cnt = 0
    for i in range(asum // d):
        cnt += d - (-heappop(q))
    if cnt <= K:
        print(d)
        exit()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()
#edge[i][j]には頂点iと頂点jをつなぐ辺の色を格納する
edge = [[0]*(n+1) for _ in range(n+1)]
#graph[i]には頂点iと繋がっている頂点を格納する
graph = [[] for _ in range(n+1)]
k = 0
a_b = []
for i in range(n-1):
    a,b = MI()
    a_b.append([a,b])
    graph[a].append(b)
    graph[b].append(a)
#check[i] == -1ならば未探索
check = [-1]*(n+1)
check[0] = 0
check[1] = 0
d = deque()
d.append(1)
while d:
    v = d.popleft()
    check[v] = 1
    cnt = 0
    for i in graph[v]:
      if check[i] != -1:
        continue
      cnt = cnt+1
      while cnt in edge[v]:
        cnt = cnt + 1
      edge[i][v] = cnt
      edge[v][i] = cnt
      d.append(i)
      check[i] = 0
      k = max(k,cnt)
print(k)
for i in range(n-1):
    color = edge[a_b[i][0]][a_b[i][1]]
    print(color)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()

#graph[i]には頂点iと繋がっている頂点を格納する
graph = [[] for _ in range(n+1)]
prev_col = [0]*(n+1)
a_b = []
k=0
for i in range(n-1):
    a,b = MI()
    a_b.append(str(a)+" "+str(b))
    graph[a].append(b)
    graph[b].append(a)
#check[i] == -1ならば未探索
check = [-1]*(n+1)
check[0] = 0
check[1] = 0
for i in range(n+1):
    k = max(len(graph[i]),k)
d = deque()
d.append(1)
ans = dict()
while d:
    v = d.popleft()
    check[v] = 1
    cnt = 0
    for i in graph[v]:
      if check[i] != -1:
        continue
      cnt = cnt+1
      if prev_col[v] == cnt:
        cnt = cnt + 1
      prev_col[i] = cnt
      ans[str(min(i,v))+" "+str(max(i,v))]=cnt
      d.append(i)
print(k)
for key in a_b:
    print(ans[key])
### BUGGY CODE ###

import numpy as np

N=int(input())

A=np.array(input().split(),dtype=np.int32)

result=[]
for sid in range(1,N+1):
    cnt=0
    for a in A:
        if(sid==a):
            cnt+=1
        elif(sid<a):
            break
    result.append(cnt)

for r in result:
    print(r)

### FIXED CODE ###

import collections

N=int(input())

A=input().split()

c=collections.Counter(A)
result=[]

for i in range(1,N+1):
    result.append(c[str(i)])

for r in result:
    print(r)
### BUGGY CODE ###

n,q = map(int,input().split())
A = [list(map(str,input().split())) for i in range(n)]
time = 0
flag = 1
while flag == 1:
    if int(A[0][1]) <= q: #プロセスが完了する場合
        time += int(A[0][1])
        print(A[0][1],time)
        del A[0]
    else: #プロセスが完了しない場合
        time += q
        A.append(A[0])
        del A[0]
    if len(A) == 0:
        flag = 0


### FIXED CODE ###

n,q = map(int,input().split())
A = [list(map(str,input().split())) for i in range(n)]
time = 0
flag = 1
while len(A) > 0:
    if int(A[0][1]) <= q: #プロセスが完了する場合
        time += int(A[0][1])
        print(A[0][0],time)
        del A[0]
    else: #プロセスが完了しない場合
        time += q
        A[0][1] = str(int(A[0][1])-q)
        A.append(A[0])
        del A[0]
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
count = 0

for i in range(N):
    while A[i] != 0 and B[i] != 0:
        A[i] -= 1
        B[i] -= 1
        count += 1
    while A[i+1] != 0 and B[i] != 0:
        A[i+1] -= 1
        B[i] -= 1
        count += 1

print(count)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
count = 0

for i in range(N):
    if A[i] != 0 and B[i] != 0:
        k = min(A[i],B[i])
        A[i] -= k
        B[i] -= k
        count += k
    if A[i+1] != 0 and B[i] != 0:
        l = min(A[i+1],B[i])
        A[i+1] -= l
        B[i] -= l
        count += l

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

n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:
  ans*=i
if ans>10**18:print(-1)
else:print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
if 0 in a:exit(print(0))
for i in a:
  ans*=i
  if ans>10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

N, M= map(int, input().split())
A = []
B = []
for i in range(N):
    a,b = map(int, input().split())
    A.append(a)
    B.append(b)
count = 0
cost = 0
while count < M:
    cost += min(A)
    count += 1
    pos = A.index(min(A))
    B[pos] -= 1
    if B[pos] <= 0:
        A.pop(pos)
        B.pop(pos)
print(cost)

### FIXED CODE ###

N, M= map(int, input().split())
A = []
for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)
A = sorted(A)
count = 0
cost = 0
i = 0
while count < M:
    cost += A[i][0] * min(A[i][1],M-count)
    count += min(A[i][1],M-count)
    i += 1    
print(cost)
### BUGGY CODE ###

import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
tree = [a[0]]

for i in range(1,n):
  tmpmin = tree[0]
  if a[i] > tmpmin:
  #  bisect.insort(tree, a[i])
  #else:
    index = bisect.bisect_left(tree, a[i])
    del tree[index - 1]
  bisect.insort(tree, a[i])
  #print(tree)
    
print(len(tree))

    


    
    

### FIXED CODE ###

import bisect
from collections import deque
n = int(input())
a = [int(input()) for _ in range(n)]
tree = deque([]) 
tree.append(a[0])

for a in a[1:]:
  index = bisect.bisect_left(tree, a)
  if index == 0:
    tree.appendleft(a)
  else:
    tree[index-1] = a
print(len(tree))
### BUGGY CODE ###

import sys
import numpy as np

n, *towns = map(int, sys.stdin.buffer.read().split())
xxx = np.array(towns[0::3], dtype=np.int64)
yyy = np.array(towns[1::3], dtype=np.int64)
ppp = np.array(towns[2::3], dtype=np.int64)

INF = 10 ** 18
ans = [INF] * (n + 1)

bit_d = ((np.arange(1 << n)[:, None] & (1 << np.arange(n)))) > 0
precalc_x = abs((xxx[None, :] * bit_d)[..., None] - xxx[None, None, :]).min(axis=1) * ppp[None, :]
precalc_y = abs((yyy[None, :] * bit_d)[..., None] - yyy[None, None, :]).min(axis=1) * ppp[None, :]
kd = bit_d.sum(axis=1)

for bit in range(1 << n):
    k = kd[bit]
    v = bit
    while v:
        ans[k] = min(ans[k], np.minimum(precalc_x[v], precalc_y[v ^ bit]).sum())
        v = (v - 1) & bit
    ans[k] = min(ans[k], np.minimum(precalc_x[0], precalc_y[bit]).sum())

print('\n'.join(map(str, ans)))


### FIXED CODE ###

import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    xxx = inp[1::3]
    yyy = inp[2::3]
    ppp = inp[3::3]

    ans = np.full(n + 1, 10 ** 18, dtype=np.int64)

    default_dist = np.zeros(n, dtype=np.int64)
    for i in range(n):
        default_dist[i] = min(abs(xxx[i]), abs(yyy[i]))

    for bit in range(1 << n):
        k = (bit & 0x5555) + (bit >> 1 & 0x5555)
        k = (k & 0x3333) + (k >> 2 & 0x3333)
        k = (k & 0x0f0f) + (k >> 4 & 0x0f0f)
        k = (k & 0x00ff) + (k >> 8 & 0x00ff)

        i = 0
        cur = 0
        t = bit
        selected = np.zeros(k, dtype=np.int64)
        is_selected = np.zeros(n, dtype=np.int8)
        while t:
            if t & 1:
                selected[cur] = i
                is_selected[i] = 1
                cur += 1
            t >>= 1
            i += 1

        for bit2 in range(1 << k):
            cost = 0
            for i in range(n):
                if is_selected[i]:
                    continue
                town_dist = default_dist[i]
                t = bit2
                for j in range(k):
                    if t & 1:
                        town_dist = min(town_dist, abs(yyy[selected[j]] - yyy[i]))
                    else:
                        town_dist = min(town_dist, abs(xxx[selected[j]] - xxx[i]))
                    t >>= 1
                cost += town_dist * ppp[i]
            kk = len(selected)
            ans[kk] = min(ans[kk], cost)

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

n = int(input())

a = (list(map(int, input().split())))
dx = 10 ** 9 + 7

# b = [i % dx for i in a]

ans = 0
alist = []
for i in range(n):
    if a[i] == 0:
        continue

    for j in range(i+1, n):
        if a[j] == 0:
            continue

        alist.append((a[i] * a[j]) % dx)

for i in range(len(alist)):
    ans += alist[i]
    ans %= dx

ans %= dx
print(ans)


### FIXED CODE ###

n = int(input())

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

S = sum(a)

S2 = sum(map(lambda x: x * x, a ))

ans = (S * S - S2) // 2 % 1000000007
print(ans)