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

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    b, c = map(int, input().split())
    for j in range(b):
        if a[0] < c:
            a[0] = c
            a.sort()
ans = sum(a)
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
bc = []
for i in range(m):
    bc.append(list(map(int, input().split())))
bc.sort(key=lambda x: x[1], reverse=True)
for i in bc:
    if a[0] < i[1]:
        for j in range(i[0]):
            if a[0] < i[1]:
                a.append(i[1])
                del a[0]
            else:
                break
    else:
        break
print(sum(a))
### BUGGY CODE ###

s = input()
t = input()
ls_s = list(s)
ls_t = list(t)
set_s = set(ls_s)
set_t = set(list(t))
if not set_t <= set_s:
    print(-1)
    exit()
tag_t = [-1]*len(t)
cnt_t = 0 #index of t
cnt = 0 #count i
tag = 0 #index of s
n = len(s)-1
nt = len(t)-1
for i in range(nt+1):
    while True:
        if ls_t[i] == ls_s[tag]:
            tag_t[i] = tag +1
            tag += 1
            if tag > n:
                tag = 0
            break
        tag += 1
        if tag > n:
            tag = 0
now = tag_t[0]
cnt+= now
for i in range(1,nt+1):
    pre = now
    now = tag_t[i]
    if now > pre:
        cnt +=  now - pre
    else:
        cnt += n+1 - pre + now
print(cnt)


### FIXED CODE ###

def sn(a):
    return ord(a) - ord("a")

def isok(idx,prev):##適宜変更
    return prev>=idx+n*loops


def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ

S = input()
T = input()
lt = list(T)
ls = list(S)
set_s = set(list(S))
set_t = set(lt)
if not set_t <= set_s:
    print(-1)
    exit()
cnts = [[] for i in range(26)]
cnts_idx = [0]*26
for i,w in enumerate(ls):
    cnts[sn(w)].append(i)

loops = 0
n = len(S)
prev = -1
for t in lt:
    idx = bisect(cnts[sn(t)],prev)+1
    if idx==len(cnts[sn(t)]):
        loops+=1
        idx = 0
    prev = cnts[sn(t)][idx] + loops*n

print(prev+1)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
count = 1
while a:
    try:
        index = a.index(count)
        count += 1
        a = a[index:]
    except ValueError:
        if count == 1:
            ans = -1
        else:
            ans = n - (count - 1)
        a = []
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
count = 0
for i in range(n):
    if a[i] == count + 1:
        count += 1
if count:
    print(n - count)
else:
    print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

min_ind = 0
min_val = 3e9
for i in range(1, N):
    tmp = A[i]+A[i-1]
    if tmp < min_val:
        min_val = tmp
        min_ind = i

# ダムmin_indから決めていく
rain = [0 for i in range(N)]
start = min_ind
end = (start+N-1)%N
lim = min(A[end], A[start]) * 2
for r in range(0, lim+1, 2):
    rain[start] = r
    now = (start+1)%N
    pre = start
    ok = False
    while now != start:
        rain[now] = (A[pre] - rain[pre] // 2) * 2
        if A[now] < rain[now]//2:
            break
        now = (now+1)%N
        pre = (pre+1)%N
    if now == start:
        if rain[now] == (A[pre] - rain[pre]//2) * 2:
            ok = True
    if ok:
        for i in range(N):
            print(rain[i], end="")
            if i != N-1:
                print(" ",end="")
            else:
                print()
        break


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

x = [0] * N
S = sum(A)
x[0] = S - 2 * (sum(A[1:N:2]))
for i in range(1, N):
    x[i] = 2 * A[i-1] - x[i-1]

for i in range(N-1):
    print(x[i], end=" ")
print(x[N-1])
### BUGGY CODE ###

n,k=map(int,input().split())
c=list(map(int,input().split()))
dp=[0 for i in range(n)]
for i in range(1,n):
    dp[i]=min([dp[j]+abs(c[i]-c[j]) for j in range(max(0,i-k),i)])
print(dp[-1])

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

mod = 998244353
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]

for i in range(2, N+1):
  g1.append((g1[-1] * i) % mod)
  inv.append((-inv[mod % i] * (mod//i)) % mod)
  g2.append((g2[-1] * inv[-1]) % mod)

ans = 0
for x in range(N+1):
  rest = K - A*x
  if rest % B == 0:
    y = rest // B
    for g in range(max(0, x+y-N), min(x,y)+1):
      r = x - g
      b = y - g
      ans += g1[N] * g2[r] * g2[g] * g2[b] * g2[N-r-g-b] % mod

print(ans % mod)

### FIXED CODE ###

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

MOD = 998244353
factorials = [1]
inv_facts = [1]
for i in range(1, N+1):
    factorials.append(factorials[-1] * i % MOD)
    inv_facts.append(inv_facts[-1] * pow(i, MOD-2, MOD) % MOD)

def combi(n, k):
    ret = factorials[n]
    ret *= inv_facts[k]
    ret %= MOD
    ret *= inv_facts[n-k]
    ret %= MOD
    return ret

ans = 0
for a in range(N+1):
    rest = K - (A * a)
    if rest < 0:
        break
    if rest % B == 0:
        b = rest // B
        if b <= N:
            tmp = combi(N, a) * combi(N, b) % MOD
            ans += tmp
            ans %= MOD
print(ans)
### BUGGY CODE ###

import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

def calc_(n):
    return n - 1

def main():
    N, K, Q = map(int, input().split())
    L_2 = [int(input()) for _ in range(Q)]

    N_points = [K for _ in range(N)]

    for i in L_2:
        N_points = list(map(calc_, N_points))
        logging.info(N_points)
        N_points[i - 1] += 1

    for i in N_points:
        if i > 0:
            print("Yes")
        else:
            print("No")

            
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)


def main():
    N, K, Q = map(int, input().split())
    L_2 = [int(input()) for _ in range(Q)]

    N_points = [0 for _ in range(N)]

    for i in L_2:
        N_points[i - 1] += 1

    for i in N_points:
        if i - (Q - K) > 0:
            print("Yes")
        else:
            print("No")

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

class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [0 for _ in range(2 * N)]

    def update(self, i, x):
        index = self.N + i - 1
        self.data[index] = x
        while index > 0:
            index = (index - 1) // 2  # parent
            self.data[index] = max(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.data[k]
        else:
            vl = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
            vr = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
            return max(vl, vr)


def main():
    N = int(input())
    pw2 = 1
    while pw2 < N:
        pw2 *= 2
    S = input()
    Q = int(input())
    query_list = [input().split(' ') for _ in range(Q)]
    trees = [None for _ in range(26)]
    for cn in range(26):
        trees[cn] = SegTree(pw2)
    for i, c in enumerate(S):
        cn = ord(c) - ord('a')
        trees[cn].update(i, 1)
    for query in query_list:
        if query[0] == '1':
            # type 1 query
            i = int(query[1]) - 1
            new_cn = ord(query[2]) - ord('a')
            for cn in range(26):
                x = (1 if cn == new_cn else 0)
                trees[cn].update(i, x)
        else:
            # type 2 query
            left = int(query[1]) - 1
            right = int(query[2]) - 1
            kinds = sum([trees[cn].query(left, right + 1, 0, 0, pw2) for cn in range(26)])
            print(kinds)


if __name__ == '__main__':
    main()


### FIXED CODE ###

class BIT:

    def __init__(self, N):
        # NOTE: 1-indexed
        self.N = N
        self.data = [0] * (N + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & (- i)
        return s

    def update(self, i, x):
        while i <= self.N:
            self.data[i] += x
            i += i & (- i)


def c2n(c):
    return ord(c) - ord('a')


def main():
    N = int(input())
    S = input()
    char_list = list(S)
    trees = [BIT(N) for _ in range(26)]
    for i, c in enumerate(S):
        trees[c2n(c)].update(i + 1, 1)
    Q = int(input())
    ans = list()
    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            _, i, c = query
            i = int(i) - 1
            before_c = char_list[i]
            char_list[i] = c
            trees[c2n(before_c)].update(i + 1, - 1)
            trees[c2n(c)].update(i + 1, 1)
        else:  # type '2'
            _, left, right = query
            left, right = int(left) - 1, int(right) - 1
            cnt = 0
            for i in range(26):
                n = trees[i].sum(right + 1) - trees[i].sum(left)
                if n > 0:
                    cnt += 1
            ans.append(cnt)
    for a in ans:
        print(a)


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

h,w=map(int,input().split())
s=[list(input())for _ in range(h)]
score=[[0]*w for _ in range(h)]
ans=0
range_w=range(w)
range_h=range(h)
r_range_w=range(w)[::-1]
r_range_h=range(h)[::-1]
for i in range_h:
  tmp=0
  for j in range_w:
    if s[i][j]=="#":
      tmp=0
    else:
      tmp+=1
    score[i][j]+=tmp
for i in range_h:
  tmp=0
  for j in r_range_w:
    if s[i][j]=="#":
      tmp=0
    else:
      tmp+=1
    score[i][j]+=tmp
for j in range_w:
  tmp=0
  for i in range_h:
    if s[i][j]=="#":
      tmp=0
    else:
      tmp+=1
    score[i][j]+=tmp
for j in range_w:
  tmp=0
  for i in r_range_h:
    if s[i][j]=="#":
      tmp=0
    else:
      tmp+=1
    score[i][j]+=tmp-3
    ans=max(ans,score[i][j])
# print(score)
print(ans)

### FIXED CODE ###

h,w=map(int,input().split())
s=[list(input())for _ in range(h)]
score=[[0]*w for _ in range(h)]
ans=0
range_w=range(w)
range_h=range(h)
for i in range_h:
  tmp_1=0
  tmp_2=0
  for j in range_w:
    if s[i][j]=="#":
      tmp_1=0
    else:
      tmp_1+=1
    score[i][j]+=tmp_1
    
    if s[i][-j-1]=="#":
      tmp_2=0
    else:
      tmp_2+=1
    score[i][-j-1]+=tmp_2
    
for j in range_w:
  tmp_3=0
  tmp_4=0
  for i in range_h:
    if s[i][j]=="#":
      tmp_3=0
    else:
      tmp_3+=1
    score[i][j]+=tmp_3
    
    if s[-i-1][j]=="#":
      tmp_4=0
    else:
      tmp_4+=1
    score[-i-1][j]+=tmp_4-3
for i in range(h):
  for j in range(w):
    ans=max(ans,score[i][j])
print(ans)
### BUGGY CODE ###

# encoding: utf-8
import itertools


n = int(input())
xlist = []
ylist = []
hlist = []
for i in range(n):
	xtmp, ytmp, htmp = map(int, input().split())
	xlist.append(xtmp)
	ylist.append(ytmp)
	hlist.append(htmp)
h = max(hlist)
end_flag = False
while True:
	for cx, cy in itertools.product(range(101), range(101)):
		if all([hlist[i] == max(h - abs(xlist[i] - cx) - abs(ylist[i] - cy), 0) for i in range(n)]):
			print('{} {} {}'.format(cx, cy, h))
			end_flag = True
			break
	if end_flag:
		break
	h += 1


### FIXED CODE ###

# encoding: utf-8
import itertools


n = int(input())
xlist = []
ylist = []
hlist = []
for i in range(n):
	xtmp, ytmp, htmp = map(int, input().split())
	xlist.append(xtmp)
	ylist.append(ytmp)
	hlist.append(htmp)
h = max(hlist)
end_flag = False
while True:
	for cx, cy in itertools.product(range(101), range(101)):
		if all([hlist[i] == max(h - abs(xlist[i] - cx) - abs(ylist[i] - cy), 0) for i in range(n)]):
			print('{} {} {}'.format(cx, cy, h))
			end_flag = True
			break
	if end_flag:
		break
	h += 1
### BUGGY CODE ###

N = int(input())
A = [abs(int(input())) for _ in range(N)]
#A.sort()
s = sum(A)

def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

mod = 998244353

dp = [[0]*(s+1) for _ in range(N)]
# dp[n][s] An-1(0-index)まで加えて、Rの和がsになるのが何通りか（残りのG,Bまで含めて）
dp[0][0] = 2
dp[0][A[0]] = 1
temp_sum = A[0]

for i in range(1,N):
  for j in range(A[i]):
    dp[i][j] = (dp[i-1][j]*2) %mod
  for j in range(A[i], temp_sum+1):
    dp[i][j] = (dp[i-1][j]*2 + dp[i-1][j-A[i]]) %mod
  for j in range(temp_sum+1, temp_sum+1 + A[i]):
    dp[i][j] = (dp[i-1][j-A[i]]) %mod
  temp_sum += A[i]


def part_sum(a,A):
  p=mod
  #初期化
  N=len(a)
  dp=[[0 for i in range(A+1)] for j in range(N+1)]
  dp[0][0]=1

  #DP
  for i in range(N):
    for j in range(A+1):
      if a[i]<=j: #i+1番目の数字a[i]を足せるかも
        dp[i+1][j]=dp[i][j-a[i]]+ dp[i][j]% p
      else: #入る可能性はない
        dp[i+1][j]=dp[i][j]%p
  return dp[N][A]

ps = part_sum(A, s//2)

if s%2 != 0:
    answer = (powermod(3, N, mod) - 3*sum(dp[N-1][(s+1)//2:]))%mod
else:
    answer = (powermod(3, N, mod) - 3*(sum(dp[N-1][(s+1)//2:]) - ps))%mod



print(answer)

### FIXED CODE ###

N = int(input())
A = [abs(int(input())) for _ in range(N)]
#A.sort()
s = sum(A)

def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

mod = 998244353

dp = [[0]*(s+1) for _ in range(N)]
# dp[n][s] An-1(0-index)まで加えて、Rの和がsになるのが何通りか（残りのG,Bまで含めて）
dp[0][0] = 2
dp[0][A[0]] = 1
temp_sum = A[0]

for i in range(1,N):
  for j in range(A[i]):
    dp[i][j] = (dp[i-1][j]*2) %mod
  for j in range(A[i], temp_sum+1):
    dp[i][j] = (dp[i-1][j]*2 + dp[i-1][j-A[i]]) %mod
  for j in range(temp_sum+1, temp_sum+1 + A[i]):
    dp[i][j] = (dp[i-1][j-A[i]]) %mod
  temp_sum += A[i]


def part_sum(a,A):
  p=mod
  #初期化
  N=len(a)
  dp=[[0 for i in range(A+1)] for j in range(N+1)]
  dp[0][0]=1

  #DP
  for i in range(N):
    for j in range(A+1):
      if a[i]<=j: #i+1番目の数字a[i]を足せるかも
        dp[i+1][j]=dp[i][j-a[i]]+ dp[i][j]% p
      else: #入る可能性はない
        dp[i+1][j]=dp[i][j]%p
  return dp[N][A]

ps = part_sum(A, s//2)

if s%2 != 0:
    answer = (powermod(3, N, mod) - 3*sum(dp[N-1][(s+1)//2:]))%mod
else:
    answer = (powermod(3, N, mod) - 3*(sum(dp[N-1][(s+1)//2:]) - ps))%mod



print(answer)
### BUGGY CODE ###

import collections
import math

N = int(input())

word_dict = []
num = []

for i in range(N):
    s = input()
    count = collections.Counter(s)
    if count in word_dict:
        num[word_dict.index(count)] += 1
    else:
        word_dict.append(count)
        num.append(0)

ans = 0

for i in num:
    i += 1
    if i >= 3:
        ans = ans + (math.factorial(i) // (math.factorial(i - 2) * math.factorial(2)))
    elif i == 2:
        ans += 1

print(ans)


### FIXED CODE ###

import collections
import math

N = int(input())
word_dict = {}

ans = 0

for _ in range(N):
    s = input()
    s = "".join(sorted(s))
    if s in word_dict:
        ans += word_dict[s]
        word_dict[s] += 1
    else:
        word_dict[s] = 1
    
print(ans)
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
bc = [list(map(int, input().split())) for _ in range(m)]

bc.sort(key=lambda x: x[1], reverse=True)
ans = 0
for b, c in bc:
    b -= 1
    i = bisect.bisect_left(a, c)
    index = min(i - 1, b) + 1
    ans += index * c
    del a[:index]
print(sum(a) + ans)


### FIXED CODE ###

import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
bc = [list(map(int, input().split())) for _ in range(m)]

bc.sort(key=lambda x: x[1], reverse=True)
ans = 0
for b, c in bc:
    b -= 1
    i = bisect.bisect_left(a, c)
    index = min(i - 1, b) + 1
    ans += index * c
    del a[:index]
print(sum(a) + ans)
### BUGGY CODE ###

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

for i in range(1,n+1):
	print(a.index(i)+1, end = " ")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
answer = [0] * n

for i in range(n):
	answer[a[i]-1] = i + 1 

for i in range(n):
	print(answer[i], end = " ")
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        prod = (a[i] * a[j]) % mod
        ans += prod
        ans %= mod

print(ans)

### FIXED CODE ###

mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
s = [0] * (n+1)

for i in range(n-1, 0, -1):
    s[i] = (a[i] + s[i+1]) % mod


ans = 0
for i in range(n-1):
    tmp = (a[i] * s[i+1]) % mod
    ans += tmp
    ans %= mod

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

S = input()
P = [0 for _ in range(len(S)+1)]
mod = 2019
d = 1
for i in range(len(S), 0, -1):
    P[i-1] = int(S[i-1])*d + P[i]
    P[i-1] = P[i-1] % mod
    d *= 10

A = [0] * 2019
for p in P:
    A[p] += 1

ans = 0
for a in A:
    ans += a*(a-1)//2
print(ans)

### FIXED CODE ###

from collections import Counter
S = input()
P = [0] * (len(S)+1)
mod = 2019
d = 1
for i in range(len(S), 0, -1):
    P[i-1] = int(S[i-1])*d + P[i]
    P[i-1] = P[i-1] % mod
    d *= 10
    d = d % mod

P = Counter(P)
ans = 0
for p in P.values():
    ans += p*(p-1)//2
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
from copy import deepcopy
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()


def main():
    R, C, K = map(int, input().split())
    items = defaultdict(list)
    for _ in range(K):
        r, c, v = map(int, input().split())
        items[r-1].append([c-1, v])
    dp = np.zeros(C,dtype=int)
    for RR in range(R):
        dptmp1 = deepcopy(dp)
        dptmp2 = deepcopy(dp)
        dptmp3 = deepcopy(dp)
        items[RR].sort(key=lambda x:x[0])
        for item in items[RR]:
            dptmp3[item[0]:] = np.clip(
                dptmp3[item[0]:], dptmp2[item[0]]+item[1], None)
            dptmp2[item[0]:] = np.clip(
                dptmp2[item[0]:], dptmp1[item[0]]+item[1], None)
            dptmp1[item[0]:] = np.clip(
                dptmp1[item[0]:], dp[item[0]]+item[1], None)
        dp=deepcopy(dptmp3)
    print(dp[-1])
            



if __name__ == '__main__':
    main()
  

### FIXED CODE ###

import sys
import numpy as np
from collections import defaultdict
from numba import njit
def input(): return sys.stdin.readline().rstrip()

@njit
def koushin(dp,item):
    dptmp1 = np.copy(dp)
    dptmp2 = np.copy(dp)
    dptmp3 = np.copy(dp)
    for i in range(len(item)):
        dptmp3[item[i][0]:] = np.fmax(dptmp3[item[i][0]:], dptmp2[item[i][0]]+item[i][1])
        dptmp2[item[i][0]:] = np.fmax(dptmp2[item[i][0]:], dptmp1[item[i][0]]+item[i][1])
        dptmp1[item[i][0]:] = np.fmax(dptmp1[item[i][0]:], dp[item[i][0]]+item[i][1])
    return dptmp3

def main():
    R, C, K = map(int, input().split())
    items = defaultdict(list)
    for _ in range(K):
        r, c, v = map(int, input().split())
        items[r-1].append([c-1, v])
    dp = np.zeros(C, dtype=int)
    for RR in range(R):
        if items[RR]==[]:
          continue
        items[RR].sort(key=lambda x: x[0])
        dp=koushin(dp,np.array(items[RR],dtype=int))
    print(dp[-1])


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

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

ans = round(n*(n-1)*(n-2)/6)
b=0

l.sort()

for i in range(n):
    for j in range(i+1,n):
        b = l[i] + l[j]
        for k in range(j+1,n):
            if b<=l[k]:
                ans-=n-k
                break

if ans<0:
    ans=0

print(ans)

### FIXED CODE ###

import bisect
n = int(input())
li = list(map(int, input().split()))

li.sort()
ans = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        ans += bisect.bisect_left(li, li[i]+li[j]) - j - 1

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

import itertools

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


A = itertools.combinations(a,2)

total = 0
for i,j in A:
    total += (i*j)
    total = total%MOD
print(total)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
 
ans = 0
total = sum(A)
for i in range(N - 1):
    total -= A[i]
    ans += (A[i] * total) 
 
print(ans % mod)
### BUGGY CODE ###

from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        n2 = n * 2
        acc = [[0] * n2]
        row = [0] * n2
        for x in rev_c:
            row[n2 - x - 1] += 1
            acc.append(list(reversed(list(accumulate(row)))))
        return acc

    # How many white/black ball lower than 'k' righter than index x? (0<=x<=2N-1)
    # cost[color][k][x]
    cost = list(map(existence_right, rev))

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for x, dp0, dp1, c0 in zip(rev[0], dp, dp[1:], cost[0]):
        dp1[0] = dp0[0] + c0[x]
    dp0 = dp[0]
    for b, (y, dp0b, c1) in enumerate(zip(rev[1], dp0, cost[1])):
        dp0[b + 1] = dp0b + c1[y]
    for x, dp0, dp1, cw0, cw1 in zip(rev[0], dp, dp[1:], cost[0], cost[0][1:]):
        cw0x = cw0[x]
        for b, (y, dp01, dp10, cb0, cb1) in enumerate(zip(rev[1], dp0[1:], dp1, cost[1], cost[1][1:])):
            dp1[b + 1] = min(dp01 + cw0x + cb1[x], dp10 + cw1[y] + cb0[y])
    return dp[n][n]


n = int(input())
# White/Black 'k' ball is what-th in whole row?
rev = [[0] * n, [0] * n]
for i in range(n * 2):
    c, a = input().split()
    a = int(a) - 1
    rev[int(c == 'B')][a] = i
print(solve(n, rev))


### FIXED CODE ###

from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        n2 = n * 2
        acc = [[0] * n2]
        row = [0] * n2
        for x in rev_c:
            row[n2 - x - 1] += 1
            acc.append(list(reversed(list(accumulate(row)))))
        return acc

    # How many white/black ball lower than 'k' righter than index x? (0<=x<=2N-1)
    # cost[color][k][x]
    cost = list(map(existence_right, rev))

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for w, x in enumerate(rev[0]):
        dp[w + 1][0] = dp[w][0] + cost[0][w][x]
    for b, y in enumerate(rev[1]):
        dp[0][b + 1] = dp[0][b] + cost[1][b][y]
    for w, x in enumerate(rev[0]):
        dpw0, dpw1 = dp[w], dp[w + 1]
        cost_wx, cost_w1 = cost[0][w][x], cost[0][w + 1]
        for b, y in enumerate(rev[1]):
            dpw1[b + 1] = min(dpw0[b + 1] + cost_wx + cost[1][b + 1][x],
                              dpw1[b] + cost_w1[y] + cost[1][b][y])
    return dp[n][n]


n = int(input())
# White/Black 'k' ball is what-th in whole row?
rev = [[0] * n, [0] * n]
for i in range(n * 2):
    c, a = input().split()
    a = int(a) - 1
    rev[int(c == 'B')][a] = i
print(solve(n, rev))
### BUGGY CODE ###

MOD = 1000000007
N = int(input())
A = list(map(int, input().split()))
ans = 0
B = [0]*(N-1)
for i in range(1, N):
    B[i-1] = sum(A[i:N])
for i in range(0, N-1):
    ans += A[i] * B[i]
    ans %= MOD
print(ans)


### FIXED CODE ###

MOD = 1000000007
N = int(input())
A = list(map(int, input().split()))
ans = 0
B = [0]*(N-1)
sumA = sum(A)
for i in range(1, N):
    sumA -= A[i-1]
    B[i-1] = sumA
for i in range(0, N-1):
    ans += A[i] * B[i]
    ans %= MOD
print(ans)
### BUGGY CODE ###

N,K=list(map(int,input().split()))
src=[n for n in range(N+1)]
ans=0
for k in range(K,N+2):
  M=sum(src[-k:])
  m=sum(src[0:k])
  ans+=M-m+1

print(ans%(10**9+7))

### FIXED CODE ###

N,K=list(map(int,input().split()))
ans=0
for k in range(K,N+2):
  M=k*N-k*(k-1)//2
  m=k*(k-1)//2
  ans+=M-m+1

print(ans%(10**9+7))