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

N, K = map(int,input().split())
H = list(map(int,input().split()))
DP = [0]*(N+1)
def dH(i,j):
  return abs(H[i-1] - H[j-1])
for i in range(2,N+1):
  DP[i] = min( [DP[j] + dH(j, i) for j in range(max(1,i-K),i)])
print(DP[N])

### FIXED CODE ###

N, K = map(int,input().split())
H = list(map(int,input().split()))
import numpy as np
dp = np.zeros(N,dtype=np.int)
harr = np.array(H)
for i in range(1,N):
  St = max(0,i-K)
  Hi = harr[i]
  dp[i] = min(dp[max(0,i-K):i] + np.abs(Hi - harr[max(0,i-K):i]))
print(dp[-1])
### BUGGY CODE ###

from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))
    return H, W, S


def bfs(yx, H, W, S):
    dirs = (1, W+2, -1, -W-2)
    visited = [0] * ((H+2) * (W+2))
    q = deque()
    q.append((yx, 0))
    max_depth = 0
    while len(q) > 0:
        yx, depth = q.popleft()
        visited[yx] = 1
        max_depth = max(max_depth, depth)
        if max_depth == H * W:
            break
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and visited[nyx] == 0:
                q.append((nyx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


### FIXED CODE ###

from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


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

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

n = int(input())

answer = 0.0

for i in range(1,n+1):
  
  for j in range(1,n+1):
    
    for h in range(1,n+1):
      f = gcd(i,j,h)
      answer += f
      
print(int(answer))

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

n = int(input())

answer = 0.0

for i in range(1,n+1):
  
  for j in range(1,n+1):
    
    for h in range(1,n+1):
      f = gcd(i,j,h)
      answer += f
      
print(int(answer))
### BUGGY CODE ###

s = input()
q = int(input())

ans = s
ret = "-1"

tcount = 0
rlist = ""
llist = ""

for i in range(q):
    qret = list(input().split())
    if qret[0] == "1":
        tcount += 1
        # ans = ans[::-1]
    else:
        f = qret[1]
        c = qret[2]
        if f == "1":
            if tcount % 2 == 0:
                llist += c
            else:
                rlist += c
        else:
            if tcount % 2 == 0:
                rlist += c
            else:
                llist += c

if tcount % 2 == 0:
    print(llist[::-1]+ans+rlist)
else:
    print(rlist[::-1]+ans[::-1]+llist)


### FIXED CODE ###

s = input()
q = int(input())

tcount = 0
rlist = ""
llist = ""

for i in range(q):
    qret = input()
    if qret[0] == "1":
        tcount += 1
        # ans = ans[::-1]
    else:
        f = qret[2]
        c = qret[4]
        if f == "1":
            if tcount % 2 == 0:
                llist = c + llist
            else:
                rlist += c
        else:
            if tcount % 2 == 0:
                rlist += c
            else:
                llist = c + llist

if tcount % 2 == 0:
    print(llist + s + rlist)
else:
    print(rlist[::-1] + s[::-1] + llist[::-1])
### BUGGY CODE ###

n = int(input())
x = 0
for a in range(1, n):
  for b in range(1, n):
    if a * b < n:
      x += 1
print(x)

### FIXED CODE ###

n = int(input())
x = 0
for a in range(1, n):
  for b in range(1, n):
    if a * b < n:
      x += 1
    elif a * b >= n:
      break
print(x)
### BUGGY CODE ###

from itertools import combinations

N = int(input())
A = list(map(int, input().split()))
index = list(range(N))
ans = 0
for combination in combinations(index, 2):
    if A[combination[0]]+A[combination[1]] == combination[1] - combination[0]:
        ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A_plus_index = list(A[i]+i+1 for i in range(N))
    A_plus_index = Counter(A_plus_index)
    index_minus_A = list(i+1-A[i] for i in range(N))
    ans = 0
    for a in index_minus_A:
        ans += A_plus_index.get(a, 0)
    print(ans)


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

import numpy as np

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

S = np.zeros((N+1, M+1), dtype='int')

for n in range(1, N+1):
    S[n, 1:] = list(map(int, list(input())))

# count nodes
N_cum = np.cumsum(np.cumsum(S, axis=0), axis=1) 
# count edges(row)
ER_cum = np.cumsum(np.cumsum(S[:N, :]*S[1:, :], axis=0), axis=1) 
# count edges(col)
EC_cum = np.cumsum(np.cumsum(S[:, :M]*S[:, 1:], axis=0), axis=1) 

sol_list = []

for _ in range(Q):
    x1, y1, x2, y2 = map(int, input().split())
    # nodes
    N_nodes = N_cum[x2, y2] - N_cum[x1-1, y2] - N_cum[x2, y1-1] + N_cum[x1-1, y1-1]
    # edges(row)
    N_edges1 = ER_cum[x2-1, y2] - ER_cum[x1-1, y2] - ER_cum[x2-1, y1-1] + ER_cum[x1-1, y1-1]
    # edges(col)
    N_edges2 = EC_cum[x2, y2-1] - EC_cum[x1-1, y2-1] - EC_cum[x2, y1-1] + EC_cum[x1-1, y1-1]
    
    sol_list.append(N_nodes - N_edges1 - N_edges2)

for q in range(Q):
    print(sol_list[q])

### FIXED CODE ###

import numpy as np

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

S = np.zeros((N+1, M+1), dtype='float32')

for n in range(1, N+1):
    S[n, 1:] = list(map(int, list(input())))

# count nodes
N_cum = np.cumsum(np.cumsum(S, axis=0), axis=1) 
# count edges(row)
ER_cum = np.cumsum(np.cumsum(S[:N, :]*S[1:, :], axis=0), axis=1) 
# count edges(col)
EC_cum = np.cumsum(np.cumsum(S[:, :M]*S[:, 1:], axis=0), axis=1) 

sol_list = []

for _ in range(Q):
    x1, y1, x2, y2 = map(int, input().split())
    # nodes
    N_nodes = N_cum[x2, y2] - N_cum[x1-1, y2] - N_cum[x2, y1-1] + N_cum[x1-1, y1-1]
    # edges(row)
    N_edges1 = ER_cum[x2-1, y2] - ER_cum[x1-1, y2] - ER_cum[x2-1, y1-1] + ER_cum[x1-1, y1-1]
    # edges(col)
    N_edges2 = EC_cum[x2, y2-1] - EC_cum[x1-1, y2-1] - EC_cum[x2, y1-1] + EC_cum[x1-1, y1-1]
    
    sol_list.append(N_nodes - N_edges1 - N_edges2)

for q in range(Q):
    print(int(sol_list[q]))
### BUGGY CODE ###

from math import gcd

N = int(input())
A = list(map(int, input().split()))
MAX = 10**6


def prime_factor_sieve(n):
    """
    エラトステネスの篩で、
    2 ~ Nの各数に対して、その整数のもつ最小の素因数
    (その整数を篩落とした最小の素因数)を記録して返す
    O(nloglog(n))
    """
    res = [i for i in range(n+1)]
    for i in range(2, int(n**0.5)+1):
        if res[i] < i:
            continue
        for j in range(i*i, n+1, i):
            if res[j] == j:
                res[j] = i
    return res

def factorization(n, min_factor):
    """
    エラトステネスの篩で手に入れた、各整数の最小素因数のリスト
    からO(log(n))で素因数分解する
    """
    res = set()
    while n > 1:
        res.add(min_factor[n])
        n //= min_factor[n]
        # 割った後の素因数についてもO(1)で参照できる
    return res

# 素因数が重複しているかを調べる
min_factor = prime_factor_sieve(MAX)
res = set()
is_ok = 1

for a in A:
    tmp = factorization(a, min_factor)
    if res & tmp:
        is_ok = 0
        break
    res = res.union(tmp)
    
if is_ok:
    print("pairwise coprime")
else:
    g = A[0]
    for i in range(1, N):
        g = gcd(g, A[i])
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")

### FIXED CODE ###

from math import gcd

N = int(input())
A = list(map(int, input().split()))
MAX = 10**6 + 1

def prime_factor_sieve(n):
    """
    エラトステネスの篩で、
    2 ~ Nの各数に対して、その整数のもつ最小の素因数
    (その整数を篩落とした最小の素因数)を記録して返す
    O(nloglog(n))
    """
    res = [i for i in range(n+1)]
    for i in range(2, int(n**0.5)+1):
        if res[i] < i:
            continue
        for j in range(i*i, n+1, i):
            if res[j] == j:
                res[j] = i
    return res

def factorization(n, min_factor, used_factor, cnt):
    """
    エラトステネスの篩で手に入れた、各整数の最小素因数のリスト
    からO(log(n))で素因数分解する
    """
    
    while n > 1:
        if used_factor[min_factor[n]] == 0:
            used_factor[min_factor[n]] = cnt
        elif used_factor[min_factor[n]] != cnt:
            return False
        n //= min_factor[n]
        # 割った後の素因数についてもO(1)で参照できる
    return True


# 素因数が重複しているかを調べる
min_factor = prime_factor_sieve(MAX)
res = set()
is_ok = 1
used_factor = [0]*(MAX+1)
cnt = 1
for a in A:
    if a == 1:
        continue
    is_ok = factorization(a, min_factor, used_factor, cnt)
    cnt += 1
    if not is_ok:
        break

if is_ok:
    print("pairwise coprime")
else:
    g = A[0]
    for i in range(1, N):
        g = gcd(g, A[i])
    if g == 1:
        print("setwise coprime")
    else:
        print("not coprime")
### BUGGY CODE ###

k = int(input())
nums = reversed([ int(s) for s in input().split(" ")])

pass_n = set([2])
for n in nums:

    # pass_n = このラウンドを通過する人数として可能性のある候補

    new_pass_n = set()
    # pass_n人通過させることが可能か？
    found=False
    for p in pass_n:
        if p % n == 0:
            # 可能
            found = True
            # このラウンドに進出する人数として可能性のある候補
            for i in range(n):
                new_pass_n.add(p + i)
            
    if not found:
        # 不可能
        print(-1)
        exit()

    pass_n = new_pass_n

print(min(pass_n), max(pass_n))

### FIXED CODE ###

k = int(input())
nums = reversed([ int(s) for s in input().split(" ")])

pass_min = 2
pass_max = 2
for n in nums:

    # pass_min = このラウンドを通過する人数の下限
    # pass_max = このラウンドを通過する人数の上限

    # pass_min以上の最小のnの倍数
    aaa = pass_min + (n - pass_min % n) % n

    # pass_max以下の最大のnの倍数
    bbb = pass_max - pass_max % n

    # 不可能チェック
    if aaa > pass_max or bbb < pass_min:
        print(-1)
        exit()
    
    pass_min = aaa
    pass_max = bbb + (n - 1)

print(pass_min, pass_max)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

# B以下の数-A未満の数→bisect(L, B) - bisect_left(L, A)
N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)

dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = 5 * 10**18

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue
    sx = set(map(get, Px[dX[l]:dX[r]+1]))
    sy = set(map(get, Py[dY[d]:dY[u]+1]))
    if len(sx.intersection(sy)) >= K:
        res = min(res, (r-l)*(u-d))

print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product, combinations
from operator import itemgetter
def inpl(): return tuple(map(int, input().split()))

N, K = inpl()
X = []
Y = []
Px = []
Py = []

for i in range(N):
    x, y = inpl()
    X.append(x)
    Y.append(y)
    Px.append((x, i))
    Py.append((y, i))

X = sorted(X)
Y = sorted(Y)

dX = {x:i for i, x in enumerate(X)}
dY = {y:i for i, y in enumerate(Y)}
Px = sorted(Px)
Py = sorted(Py)

get = itemgetter(1)
res = 5 * 10**18

for (l, r), (d, u) in product(combinations(X, 2), combinations(Y, 2)):
    if (dX[r] - dX[l] < K-1) or (dY[u] - dY[d] < K-1):
        continue
    if res < (r-l)*(u-d):
        continue

    sx = set(map(get, Px[dX[l]:dX[r]+1]))
    sy = set(map(get, Py[dY[d]:dY[u]+1]))
    if len(sx.intersection(sy)) >= K:
        res = min(res, (r-l)*(u-d))

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

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
abd = sorted([[e[0], e[1], e[0]+e[1]] for e in ab], key=lambda x:x[2], reverse=True)

res = 0
for i in range(n):
    abi = abd.pop(0)
    if i % 2 == 0:
        res += abi[0]
    else:
        res -= abi[1]

print(res)

### FIXED CODE ###

n = int(input())
dd = []
sb = 0
for _ in range(n):
    a, b = map(int, input().split())
    dd.append(a+b)
    sb -= b

abd = sorted(dd, reverse=True)

res = 0
for i in range(n):
    d = abd.pop(0)
    if i % 2 == 0:
        res += d

print(res+sb)
### BUGGY CODE ###

S = input()
Q = int(input())


flip = 0
for _ in range(Q):
    q = input()
    if q == '1':
        flip += 1
    else:
        _, f, c = q.split(' ')
        if f == '1' and (flip % 2) == 0:
            S = c + S
        elif f == '1' and (flip % 2) != 0:
            S = S + c
        elif f != '1' and (flip % 2) == 0:
            S = S + c
        else:
            S = c + S

if (flip % 2) == 0:
    print(S)
else:
    print(S[::-1])


### FIXED CODE ###

S = input()
Q = int(input())


flip = 0
head = ""
for _ in range(Q):
    q = input()
    if q == '1':
        flip += 1
    else:
        _, f, c = q.split(' ')
        if f == '1' and (flip % 2) == 0:
            # S = c + S
            head = head + c
        elif f == '1' and (flip % 2) != 0:
            S = S + c
        elif f != '1' and (flip % 2) == 0:
            S = S + c
        else:
            # S = c + S
            head = head + c

if (flip % 2) == 0:
    head = head[::-1]
    S = head + S
else:
    S = S[::-1]
    S = S + head

print(S)
### BUGGY CODE ###

n=int(input())
segSize=n+1
def init_max(init_max_val):
    for i in range(segSize):
        seg_max[i+num_max-1]=init_max_val[i]
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res
ide_ele_max = 0
num_max =2**(segSize-1).bit_length()
seg_max=[ide_ele_max]*2*num_max
mod=998244353

XD=[tuple(map(int,input().split()))for i in range(n)]
XD.sort()
X=[x for x,d in XD]

from bisect import bisect_right
X=[bisect_right(X,x+d-1)for x,d in XD]

init_max(list(range(segSize)))
update_max(n,n)
combs=[1]*(n+1)
P=[0]*n
t=0
for x,d in XD[::-1]:
    idx=n-1-t
    t+=1
    p=X[idx]
    p=query_max(idx,p)
    update_max(idx,p)
    P[idx]=p
for i in range(n-1,-1,-1):
    combs[i]=(combs[P[i]+1]+combs[i+1])%mod
print(combs[0])


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n=int(readline())
segSize=n+1
def init_max(init_max_val):
    for i in range(segSize):
        seg_max[i+num_max-1]=init_max_val[i]
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res
ide_ele_max = 0
num_max =2**(segSize-1).bit_length()
seg_max=[ide_ele_max]*2*num_max
mod=998244353

m = map(int,read().split())
XD = sorted(zip(m,m))
X=[x for x,d in XD]

from bisect import bisect_right
X=[bisect_right(X,x+d-1)for x,d in XD]

init_max(list(range(segSize)))
update_max(n,n)
combs=[1]*(n+1)
t=0
for x,d in reversed(XD):
    idx=n-1-t
    t+=1
    p=X[idx]
    p=query_max(idx,p)
    update_max(idx,p)
    combs[idx]=(combs[p+1]+combs[idx+1])%mod
print(combs[0])
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
comp = []
for _ in range(M):
    B, C = map(int, input().split())
    tmp = [C] * B
    comp.extend(tmp)

A.sort()
comp.sort(reverse=True)

zeros = [0] * N
comp.extend(zeros)
comp = comp[:N]

for i in range(N):
    if A[i] < comp[i]:
        A[i] = comp[i]
            
print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [int(a) * (-1) for a in input().split()]

B_array = []
for _ in range(M):
    B, C = map(int, input().split())
    B_array.append([C * (-1), B])
B_array.sort()

cnt = 0
i = 0
B_list = []
while cnt < N and i < M:
    B_list.extend([B_array[i][0]] * B_array[i][1])
    cnt += B_array[i][1]
    i += 1

A.extend(B_list)
heapq.heapify(A)

ans = 0
for _ in range(N):
    ans += heapq.heappop(A)
        
print(ans * (-1))
### BUGGY CODE ###

N, M = map(int, input().split())
edge = []
for i in range(M):
    a,b,c = map(int, input().split())
    edge.append((a-1,b-1, c))
point = [None] * N
point[0] = 0
for i in range(N*2):
    for a,b,c in edge:
        if point[a] is not None:
            if point[b] is None:
                point[b] = point[a] + c
            point[b] = max(point[b], point[a] + c)
current_point = point[N-1]
for i in range(N):
    for a,b,c in edge:
        if point[a] is not None:
            if point[b] is None:
                point[b] = point[a] + c
            point[b] = max(point[b], point[a] + c)
if current_point < point[N-1]:
    print("inf")
else:
    print(current_point)


### FIXED CODE ###

N, M = map(int, input().split())
edge = []
for i in range(M):
    a,b,c = map(int, input().split())
    edge.append((a-1,b-1, c))
point = [None] * N
point[0] = 0
for i in range((N*4)//3):
    for a,b,c in edge:
        if point[a] is not None:
            if point[b] is None:
                point[b] = point[a] + c
            point[b] = max(point[b], point[a] + c)
current_point = point[N-1]
for i in range(5):
    for a,b,c in edge:
        if point[a] is not None:
            if point[b] is None:
                point[b] = point[a] + c
            point[b] = max(point[b], point[a] + c)
if current_point < point[N-1]:
    print("inf")
else:
    print(current_point)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split(" ")))
L.sort() #小さい順
counter = 0

for num_1, i in enumerate(L):
  for num_2, j in enumerate(L):
    if num_1 >= num_2:
      continue
    else:
      for num_3, k in enumerate(L):
        if num_2 >= num_3:
          continue
        else:
          if i + j <= k:
            break
          else:
            counter += 1
print(counter)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split(" ")))
L.sort() #小さい順
counter = 0

for i in range(N-2):
  for j in range(i+1, N-1):
    index = bisect.bisect_left(L, L[i]+L[j], 0, N)
    counter = counter + index - j - 1
       
print(counter)
### BUGGY CODE ###

# problem D 
s = input()
Q = int(input())
    
summ = 0
    
for i in range(Q):
    # input をforの中に組み込む
    query = input().split()
    if query[0] == '1':
        summ += 1
    else:
        if(summ % 2 == 0 and query[1] == '1') or (summ % 2 == 1 and query[1] == '2'):
            s = ''.join([query[2],s])
        else:
            s = ''.join([s,query[2]])
    
if summ % 2 == 1:
    s = s[::-1]
        
print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
Q = int(input())
    
t = True
    
for i in range(Q):
    query = input().split()
    if query[0] == '1':
        t = not t
    else:
        if(t and query[1] == '1') or (not t and query[1] == '2'):
            s.appendleft(query[2])
        else:
            s.append(query[2])
            
s = ''.join(s)
    
if not t:
    s = s[::-1]
        
print(s)
### BUGGY CODE ###

#!/usr/bin/env python3
import bisect

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    S = list(input())
    Q = int(input())

    alphabets = [chr(i) for i in range(ord("a"), ord("a")+26)]
    L = [[] for x in alphabets] # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。

    for idx, s in enumerate(S):
        L[ord(s)-ord("a")].append(idx)

    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            y, z = int(row[1])-1, row[2]
            target = S[y]
            idx_del = bisect.bisect_left(L[ord(target)-ord("a")], y)
            if idx_del < len(L[ord(target)-ord("a")]):
                L[ord(target)-ord("a")].pop(idx_del)
            bisect.insort(L[ord(z)-ord("a")], y)
            S[y] = z

        elif row[0] == '2':
            y, z = int(row[1]) - 1, int(row[2]) - 1
            answer = 0
            for alphabet in alphabets:
                left = bisect.bisect_left(L[ord(alphabet)-ord("a")], y)
                if left < len(L[ord(alphabet)-ord("a")]) and y <= L[ord(alphabet)-ord("a")][left] <= z:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import bisect

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    S = list(input())
    Q = int(input())

    L = [[] for x in range(26)] # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。

    for idx, s in enumerate(S):
        L[ord(s)-ord("a")].append(idx)

    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            y, z = int(row[1])-1, row[2]
            if S[y] != z:
                idx_target = ord(S[y]) - ord("a")
                idx_del = bisect.bisect_left(L[idx_target], y)
                if idx_del < len(L[idx_target]):
                    L[idx_target].pop(idx_del)
                bisect.insort(L[ord(z) - ord("a")], y)
                S[y] = z

        elif row[0] == '2':
            y, z = int(row[1]) - 1, int(row[2]) - 1
            answer = 0
            for idx_alphabet in range(26):
                left = bisect.bisect_left(L[idx_alphabet], y)
                if left < len(L[idx_alphabet]) and y <= L[idx_alphabet][left] <= z:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

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

import numpy as np
import itertools as it

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

sum1 = 0
for i in range(n - 1):
    #print(a[i + 1:], a[i])
    #print(sum(a[i + 1:]))
    sum1 += a[i] * sum(a[i + 1:])

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

# sum = 0
# for i in range(n):
#     sum += 1 / a[i]
#print(sum)

# ans = int(sum * np.prod(a))
# print(ans % (10 ** 9 + 7))


### FIXED CODE ###

# import numpy as np
# import itertools as it

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

res = 0
for i in range(n):
    res += a[i] * a[i]

ans = sum(a) * sum(a)
print(((ans - res)//2) % (10 ** 9 + 7))


# sum = 0
# for i in range(n):
#     sum += 1 / a[i]
#print(sum)

# ans = int(sum * np.prod(a))
# print(ans % (10 ** 9 + 7))