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

N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]


def solve(X):
    if not ("1" in X and "2" in X and "3" in X):
        return 1e10

    MS = [[L[i] for i in range(N) if X[i] == j] for j in "123"]
    ret = 1e10
    ret = min(ret, solve2(MS[0], A) + solve2(MS[1], B) + solve2(MS[2], C))
    ret = min(ret, solve2(MS[0], A) + solve2(MS[2], B) + solve2(MS[1], C))
    ret = min(ret, solve2(MS[1], A) + solve2(MS[0], B) + solve2(MS[2], C))
    ret = min(ret, solve2(MS[1], A) + solve2(MS[2], B) + solve2(MS[0], C))
    ret = min(ret, solve2(MS[2], A) + solve2(MS[0], B) + solve2(MS[1], C))
    ret = min(ret, solve2(MS[2], A) + solve2(MS[1], B) + solve2(MS[0], C))
    return ret


def solve2(M, target):
    def rec(Y, target):
        # Y: [1, 0, 0]
        if len(Y) == len(M):
            if len(set(Y)) == 1 and Y[0] == 0:
                return 1e10
            sum_M = sum([M[i] for i in range(len(M)) if Y[i] == 1])
            return abs(target - sum_M) + 10 * (Y.count(1) - 1)
        return min(rec(Y + [0], target), rec(Y + [1], target))
    ret = rec([], target)
    return ret


ans = 1e10


def rec(X):
    global ans
    if len(X) == N:
        ans = min(ans, solve(X))
        return
    rec(X + "1")
    rec(X + "2")
    rec(X + "3")


rec("")

print(ans)


### FIXED CODE ###

N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]


def solve(X):
    if not ("1" in X and "2" in X and "3" in X):
        return 1e10

    MS = [[L[i] for i in range(N) if X[i] == j] for j in "123"]
    ret = 1e10
    A_ans = []
    B_ans = []
    C_ans = []
    for i in range(3):
        A_ans.append(solve2(MS[i], A))
        B_ans.append(solve2(MS[i], B))
        C_ans.append(solve2(MS[i], C))
    ret = min(ret, A_ans[0] + B_ans[1] + C_ans[2])
    ret = min(ret, A_ans[0] + B_ans[2] + C_ans[1])
    ret = min(ret, A_ans[1] + B_ans[0] + C_ans[2])
    ret = min(ret, A_ans[1] + B_ans[2] + C_ans[0])
    ret = min(ret, A_ans[2] + B_ans[0] + C_ans[1])
    ret = min(ret, A_ans[2] + B_ans[1] + C_ans[0])
    return ret


def solve2(M, target):
    def rec(Y, target):
        # Y: [1, 0, 0]
        if len(Y) == len(M):
            if len(set(Y)) == 1 and Y[0] == 0:
                return 1e10
            sum_M = sum([M[i] for i in range(len(M)) if Y[i] == 1])
            return abs(target - sum_M) + 10 * (Y.count(1) - 1)
        return min(rec(Y + [0], target), rec(Y + [1], target))
    ret = rec([], target)
    return ret


ans = 1e10


def rec(X):
    global ans
    if len(X) == N:
        ans = min(ans, solve(X))
        return
    rec(X + "1")
    rec(X + "2")
    rec(X + "3")


rec("")

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

n,k = map(int,input().split())

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

max_sum = 0
max_where = 0

for i in range(0,n-k+1):
    temp_sum =0
    for j in range(k):
        temp_sum += ((p[i + j] + 1) * p[i + j] / 2) / p[i + j]

    if temp_sum > max_sum:
        max_sum = temp_sum

print(max_sum)




#n,k = map(int,input().split())
#
#p = list(map(int,input().split()))
#
#max_sum = 0
#max_where = 0
#
##pi ~ pi+2の合計が最大のものが期待値も最大になる。
#for i in range(0,n-k+1):
#    temp_sum = sum(p[i:i+k])
#    if temp_sum > max_sum:
#        max_sum = temp_sum
#        max_where = i
#
#result = 0
#
#for j in range(k):
#    result += ((p[max_where + j] + 1) * p[max_where + j] / 2) / p[max_where + j]
#
#print(result)

### FIXED CODE ###

from copy import deepcopy

n,k = map(int,input().split())

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


max_sum = 0
temp_sum = 0

#最初の一組目を計算
for j in range(k):
    temp_sum += ((p[j] + 1) * p[j] / 2) / p[j]

if n == k:
    max_sum = temp_sum
    print(max_sum)

else:
    #2組目以降を計算
    for i in range(1,n-k+1):
        temp_sum = temp_sum - ((p[i-1] + 1) * p[i-1] / 2) / p[i-1] + ((p[i+k-1] + 1) * p[i+k-1] / 2) / p[i+k-1]

        if temp_sum > max_sum:
            max_sum = temp_sum


    print(max_sum)




#n,k = map(int,input().split())
#
#p = list(map(int,input().split()))
#
#max_sum = 0#for j in range(k):
#    result += ((p[max_where + j] + 1) * p[max_where + j] / 2) / p[max_where + j]
#max_where = 0
#
##pi ~ pi+2の合計が最大のものが期待値も最大になる。
#for i in range(0,n-k+1):
#    temp_sum = sum(p[i:i+k])
#    if temp_sum > max_sum:
#        max_sum = temp_sum
#        max_where = i
#
#result = 0
#

#
#print(result)
### BUGGY CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    C = [int(input()) for _ in range(N)]

    dp = [1] * (N + 1)
    dp[0] = 1
    D = {}
    pre = -1
    for n in range(N):
        c = C[n] 
        S = D.setdefault(c, set())
        dp[n + 1] = dp[n]
        if pre == c:
            dp[n] = 0
            continue
        for s in S:
            dp[n + 1] = (dp[n + 1] + dp[s]) % mod 
        pre = c
        D.setdefault(c, set()).add(n)
    print(dp[-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    mod = 10 ** 9 + 7
    N = int(input())

    dp = [1] * (N + 1)
    dp[0] = 1
    D = {}
    pre = -1
    for n in range(N):
        c = int(input())
        dp[n + 1] = dp[n]
        if pre == c:
            dp[n] = 0
            continue
        r = D.setdefault(c, 0)
        dp[n + 1] = (dp[n + 1] + r) % mod
        D[c] = r + dp[n]
        pre = c
    print(dp[-1])


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

n,k=map(int,input().split())
s=list(map(int,list(input())))
t=[1 if s[0]==1 else -1]
ans=0
for i in range(1,n):
    if s[i]==s[i-1]:
        t[-1]+=1 if s[i]==1 else -1
    else:
        t+=[1 if s[i]==1 else -1]
for i in range(len(t)):
    temp=0
    l=k*2+1 if t[i]>0 else k*2
    for j in range(l):
        if 0<=i+j<len(t):
            temp+=abs(t[i+j])
    ans=max(ans,temp)
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
s=list(map(int,list(input())))
t=[0]+[1 if s[0]==1 else -1]
ans=0
for i in range(1,n):
    if s[i]==s[i-1]:
        t[-1]=i+1 if s[i]==1 else -i-1
    else:
        t+=[i+1 if s[i]==1 else -i-1]
for i in range(len(t)-1):
    temp=0
    l=k*2+1 if t[i+1]>0 else k*2
    temp=abs(t[min(len(t)-1,i+l)])-abs(t[i])
    ans=max(ans,temp)
print(ans)
### BUGGY CODE ###

class Ship:
    def __init__(self, land_from, land_to):
        self.land_from = land_from - 1
        self.land_to = land_to - 1

N, M = map(int, input().split())

ships = []
for _ in range(M):
    f, t = map(int, input().split())
    ships.append(Ship(f, t))

# 到達可能島リストに変化があったか？
is_updated = True
# 到達可能島リスト
reachable_islands = [float('inf') for _ in range(N)]
# 初期位置は到達可能なのでTrue
reachable_islands[0] = 0

# 新たな島に移動できたなら次も探索する
while is_updated:
    is_updated = False
    # 各到達可能な島ごとに移動シミュレーション
    for island_num in range(N):
        # 到達し得ない島ならシミュレーションをスキップ
        if reachable_islands[island_num] == float('inf'):
            continue
        # 全ての船についてシミュレート
        for ship in ships:
            # 現在地の島発の船かつ目標島が到達済みでなければ移動シミュレート実行
            if island_num == ship.land_from and reachable_islands[ship.land_to] == float('inf'):
                # 到達済の印をつける
                reachable_islands[ship.land_to] = reachable_islands[ship.land_from] + 1
                # 島が更新されたフラグを立てる
                is_updated = True

# 最後の島が到達可能であるかを判定
if reachable_islands[N - 1] <= 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


### FIXED CODE ###

class Ship:
  def __init__(self, land_from, land_to):
    self.land_from = land_from - 1
    self.land_to = land_to - 1

N, M = map(int, input().split())

mid_from = set()
mid_to = set()

ships = []
for _ in range(M):
  f, t = map(int, input().split())
  ship = Ship(f, t)
  if ship.land_from == 0:
    mid_from.add(ship.land_to)
  if ship.land_to == N - 1:
    mid_to.add(ship.land_from)

# 最後の島が到達可能であるかを判定
if mid_from & mid_to:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

# Mo's algorithm
# 行ったり来たりバージョン
import sys
from math import sqrt

input = sys.stdin.buffer.readline

n, q = map(int, input().split())
C = list(map(int, input().split()))
bucket_size = int(sqrt(n))
LR = [[] for _ in range(n // bucket_size + 1)]
lmax = 0
for i in range(q):
    l, r = map(int, input().split())
    LR[l // bucket_size].append((r, l, i))
    lmax = max(lmax, l)

num = 0
count = [0] * (n + 1)


def add_num(idx):
    global num
    c = C[idx]
    if not count[c]:
        num += 1
    count[c] += 1


def del_num(idx):
    global num
    c = C[idx]
    count[c] -= 1
    if not count[c]:
        num -= 1


# 開区間[nl,nr)で考える
nl, nr = 0, 0
ans = [0] * (q)
preb = -1
for i in range(lmax // bucket_size + 1):
    query = LR[i]
    if not query:
        continue
    query.sort(reverse=(i % 2 == 1))
    for r, l, idx in query:
        l -= 1
        # 区間を広げる時
        while nl > l:
            nl -= 1
            add_num(nl)
        while nr < r:
            add_num(nr)
            nr += 1
        # 区間を狭める時
        while nl < l:
            del_num(nl)
            nl += 1
        while nr > r:
            nr -= 1
            del_num(nr)
        ans[idx] = num


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


### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    # l,rは0-indexに戻す
    l -= 1
    r -= 1
    while idx < r + 1:  # rになるまで増やす
        if idx < n:  # n超えないように注意
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

print(*ans, sep="\n")
### BUGGY CODE ###

def calc_lcs(X, Y):
    from array import array
    max_lcs = 0
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = array('I', [0] * (1001 * 1001))
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i*1001 + j] = c[(i-1)*1001 + j - 1] + 1
            elif c[(i-1)*1001 + j] >= c[i*1001 + j - 1]:
                c[i*1001 + j] = c[(i-1)*1001 + j]
            else:
                c[i*1001 + j] = c[i*1001 + j - 1]
            max_lcs = max(max_lcs, c[i*1001 + j])
    return max_lcs


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    # f = open('input.txt')
    # num = int(f.readline())

    for _ in range(num):
        X = input()
        Y = input()
        # X = f.readline().strip()
        # Y = f.readline().strip()

        # ???????????????
        result = calc_lcs(X, Y)

        # ???????????¨???
        print(result)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

最長共通部分列
"""


c = []
def prep_array(X, Y):
    global c
    """ 値が0の2次元配列を用意する。サイズは入力データの最大値を想定して縦横(1000+1)以上必要。 """
    # from array import array
    # c = [array('I', [0] * (len(X)+1)) for _ in range(len(Y)+1)]  #  arrayで用意
    c = [[0]*(len(Y)+2) for _ in range(len(X)+2)] #  リストで用意
    return c


def check_max(array):
    """ 2次元配列の中の最大の値を返す """
    max_lcs = 0
    for row in array:
        temp_max = max(row)
        if temp_max > max_lcs:
            max_lcs = temp_max
    return max_lcs


def calc_lcs4(X, Y, c):
    """
    Y[j]のアクセス方法を変更
    リストの値を一旦変数に保存するように変更
    最長共通部分長を関数内で計算するように変更
    4/5 のテストデータを使用してプロファイリングすると実効時間は 5.6秒
    """
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)
    max_lcs = 0

    pre_row = c[0]
    for i in range(1, m):
        row = c[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row
    return max_lcs


if __name__ == '__main__':
    # データの入力
    num = int(input())
    #f = open('input.txt')
    #num = int(f.readline())

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        # 処理の実行
        result = calc_lcs4(X, Y, prep_array(X, Y))

        # 結果の表示
        print(result)
### BUGGY CODE ###

s = input()
ans = 0
def united(stri):
    for a in stri:
        if a != stri[0]:
            return False
    return True

while (not united(s)) and len(s) >= 2:
    k = len(s)
    if k == 2:
        if s[0] != s[1]:
            ans += 2
        break
    for i in range(0,k-2):
        if s[i] != s[i+1]:
            if i == k - 2:
                s = s[:i]
            elif i == 0:
                s = s[i+2:]
            else:
                s = s[:i] + s[i+2:]
            ans += 2
            break
print(ans)

### FIXED CODE ###

s = input()
c_0 = 0
c_1 = 0
for i in s:
    if i == "0":
        c_0 += 1
    elif i == "1":
        c_1 += 1
print(min(c_0,c_1)*2)
### BUGGY CODE ###

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

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

A.sort()
BC.sort(key=lambda bc: bc[1], reverse=True)
update_bc = [0 for _ in range(N)]
cnt = 0
for b, c in BC:
    for i in range(b):
        if cnt < N:
            update_bc[cnt] = c
            cnt += 1
for i in range(N):
    if A[i] < update_bc[i]:
        A[i] = update_bc[i]
    else:
        break
print(sum(A))


### FIXED CODE ###

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

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

A.sort()
BC.sort(key=lambda bc: bc[1], reverse=True)
update_bc = [0 for _ in range(N)]
cnt = 0
for b, c in BC:
    for i in range(b):
        if cnt < N:
            update_bc[cnt] = c
            cnt += 1
        else:
            break
    if cnt >= N:
        break
for i in range(N):
    if A[i] < update_bc[i]:
        A[i] = update_bc[i]
    else:
        break
print(sum(A))
### BUGGY CODE ###

n, m = map(int, input().split(" "))
min = 1
for i in range(2, (int)(m/n + 1)):
  if m % i == 0:
    min = i
print(min)

### FIXED CODE ###

def make_divisors(n):
    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)

    divisors.sort()
    return divisors

n, m = map(int, input().split(" "))
max = 1
#print(make_divisors(m))
for i in make_divisors(m):
  if i > m/n:
    break
  else:
    max = i
print(max)
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
Min = min(a)-1
Max = max(a)+1
num = [[0 for i in range(N)] for j in range(Min, Max+1)]

idx = 0
for i in a:
    num[i-Min-1][idx] = 1
    num[i-Min][idx] = 1
    num[i-Min+1][idx] = 1
    idx += 1

ct = -1
for i in num:
    tmp = i.count(1)
    if tmp > ct:
        ct = tmp
        
print(ct)
        

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
Min = min(a)-1
Max = max(a)+1
ans = [0 for i in range(Min, Max+1)]

for i in a:
    ans[i-Min-1] += 1
    ans[i-Min] += 1
    ans[i-Min+1] += 1
        
print(max(ans))
### BUGGY CODE ###

N=int(input())
E=[[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)
MOD=10**9+7

#dp=子ノードの数+1(自分)
root=0
dp=[1]*N
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node
    for node in reversed(order):
        if root!=node:
            dp[parent[node]]+=dp[node]

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(1<<(N-1),MOD-2,MOD)
    for i in range(N):
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=(1<<size)-1
                p1%=MOD
            p=1-(p0*p1)
            p%=MOD
            #頂点iが白の確率
            p=p*inv2%MOD
        ans+=p
        ans%=MOD
    print(ans)

dfs()
solve()


### FIXED CODE ###

N=int(input())
E=[[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)
MOD=10**9+7

#dp=子ノードの数+1(自分)
dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

pow2=[1]*(N+1)
for i in range(1,len(pow2)):
    pow2[i]=pow2[i-1]*2%MOD

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(pow2[N-1],MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=pow2[size]-1
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()
### BUGGY CODE ###

# ABC132 E
from collections import deque

f=lambda:map(int,input().split())
N,M=f()
G=[[] for _ in [0]*(N+1)]
for _ in [0]*M:
    a,b=f()
    G[a].append(b)
S,T=f()
    
def check(i):
    res=[i]
    for i in range(3):
        tmpF=set([])
        for r in res:
            for node in G[r]:
                if node in tmpF:
                    continue
                tmpF.add(node)
        res=list(tmpF)
    return res

KKP=[[]]+[check(i+1) for i in range(N)]

F=set([])
q=deque()
q.append((S,0))
res=-1
while q:
    node,score=q.popleft()
    if node in F:
        continue
    if T==node:
        res=score
        break
    F.add(node)
    for nnode in KKP[node]:
        if nnode in F:
            continue
        q.append((nnode,score+1))
    if T in F:
        break
print(res)

### FIXED CODE ###

# ABC132 E
from collections import deque

f=lambda:map(int,input().split())
N,M=f()
G=[[] for _ in [0]*(N+1)]

for _ in [0]*M:
    a,b=f()
    G[a].append(b)
S,T=f()
S=(S,0)
T=(T,0)

q=deque()
q.append(S)
F=set()
res=-1
while q:
    node,r=q.popleft()
    if (node,r%3) in F:
        continue
    if (node,r%3) == T:
        res=r//3
        break
    F.add((node,r%3))
    for next_node in G[node]:
        if (next_node,(r+1)%3) in F:
            continue
        q.append((next_node,r+1))
print(res)
### BUGGY CODE ###

N, M = map(int, input().split())

B = [list(map(int, input().split())) for _ in range(M)][::-1]

class Group:
    id = 0
    def __init__(self):
        self.id = Group.id
        Group.id += 1
        self.root = None
        self.count = 1
        self.children = [self]

    def top(self):
        w = self
        while not w.root is None:
            w = w.root
        return w

    def addMember(self):
        self.count += 1

    def union(self, g):
        self.top().count += g.top().count
        self.top().children.extend(g.top().children)
        for x in g.top().children:
            x.root = self.top()

    def __repr__(self):
        w = self.top()
        return str(("Gropup", w.id, w.count))

pt = []
G = [Group() for x in range(N+1)]
idx = 0
cnt = 0
for x, y in B:
    wx = G[x]
    wy = G[y]
    if wx.top() is wy.top():
        pt.append(0)
    else:
        pt.append(wx.top().count * wy.top().count)
        wx.union(wy)

    #print(G)

cnt = 0
for x in pt[::-1]:
    cnt += x
    print(cnt)


### FIXED CODE ###

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

pt = []
G = [[None, 1] for x in range(N+1)]

def find(x):
    n = G[x]
    c = []
    while not n[0] is None:
        c.append(n)
        n = n[0]
    for ci in c:
        ci[0] = n
    return n

cnt = 0
while len(B):
    x, y = B.pop()
    wx = find(x)
    wy = find(y)
    if wx is wy:
        pt.append(0)
    else:
        pt.append(wx[1] * wy[1])
        wx[1] += wy[1]
        wy[0] = wx

    #print(G)

cnt = 0
for _ in range(M):
    cnt += pt.pop()
    print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
N = int(input())
A = list(map(int,input().split()))
bmin = float('inf')
bmax = float('inf')*-1
for i in range(N):
    bmin = min(bmin,A[i]-i-1)
    bmax = max(bmax,A[i]-i-1)
sadness = float('inf')
for bi in range(bmin,bmax+1):
    ans = 0 
    for i in range(N):
        ans += abs(A[i]-i-1-bi)
    sadness = min(sadness,ans)
print(sadness)

### FIXED CODE ###

import sys
import numpy as np
import math
import copy
input = sys.stdin.readline
 
N = int(input())
A = np.array(list(map(int,input().split())))
if N ==1:
    ans = 0
else:
    r = np.array(list(range(1,N+1)))
    B = np.array(sorted(A-r))
    ans = float('inf')
    for i in range(max(N//2-1,0),min(N//2+2,N)):
        c = list(map(abs,(B - B[i])))
        ans = min(ans,sum(c))
print(ans)
### BUGGY CODE ###

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

for i in range(n):
    b = [a[j] for j in range(len(a)) if j != i]
    count = b[0]
    for k in b[1:]:
        count ^= k
    print(count, end=' ')
print()




### FIXED CODE ###

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

count = 0
for k in a:
    count ^= k


for i in range(n):
    count ^= a[i]
    print(count, end=' ')
    count ^= a[i]
print()
### BUGGY CODE ###

import itertools

n = int(input())
a_list = list(map(int, input().split()))
result = []

for a in itertools.combinations(a_list, 2):
    b, c = a
    result.append(b * c)

print(sum(result) % 1000000007)

### FIXED CODE ###

mod = 10 ** 9 + 7
n = int(input())
a_list = list(map(int, input().split()))
result = 0
a_sum = sum(a_list)
for i in a_list:
    a_sum -= i
    result += i * a_sum
print(result % mod)