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


H, W = map(int, input().split())
edges = [["#" for i in range(W+2)]] + [["#"] + [None for i in range(W)] + ["#"] for j in range(H)] + [["#" for i in range(W+2)]]

for i in range(1, H+1):
  S = input()
  for j in range(1, W+1):
    edges[i][j] = S[j-1]

def dfs(x, y):
  flag = 1

  for next in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
    a, b = next
    while edges[b][a] == ".":
      flag += 1
      if x - a > 0:
        a -= 1
      elif x - a < 0:
        a += 1
      elif y - b > 0:
        b -= 1
      elif y - b < 0:
        b += 1
  
  return flag

ans = -1
for h in range(1, H+1):
  for w in range(1, W+1):
    if edges[h][w] == "#":
      continue
    flag = dfs(w, h)
    ans = max(ans, dfs(w, h))

print(ans)

### FIXED CODE ###


H, W = map(int, input().split())
S = ["#" * (W + 2)] + ["#" + input() + "#" for _ in range(H)] + ["#" * (W + 2)]

LEFT = [[0 for j in range(W+2)] for i in range(H+2)]
RIGHT = [[0 for j in range(W+2)] for i in range(H+2)]
UP = [[0 for j in range(W+2)] for i in range(H+2)]
DOWN = [[0 for j in range(W+2)] for i in range(H+2)]

for h in range(H+2):
  for w in range(W+2):
    if S[h][w] == ".":
      LEFT[h][w] = LEFT[h][w-1] + 1
    else:
      LEFT[h][w] = 0

for h in range(H+2):
  for w in range(W+2)[::-1]:
    if S[h][w] == ".":
      RIGHT[h][w] = RIGHT[h][w+1] + 1
    else:
      RIGHT[h][w] = 0

for h in range(H+2)[::-1]:
  for w in range(W+2):
    if S[h][w] == ".":
      UP[h][w] = UP[h+1][w] + 1
    else:
      UP[h][w] = 0

for h in range(H+2):
  for w in range(W+2):
    if S[h][w] == ".":
      DOWN[h][w] = DOWN[h-1][w] + 1
    else:
      DOWN[h][w] = 0

ans = -1

for h in range(H+2):
  for w in range(W+2):
    value = RIGHT[h][w] + LEFT[h][w] + UP[h][w] + DOWN[h][w] - 3
    ans = max(ans, value)

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

words = lambda t : list(map(t, input().split()))
n = int(input())
xs = words(int)

ys = []
n = 0
for x in xs:
    y = list(reversed(bin(x)))[:-2]
    ys.append(y)
    n = max(n, len(y))
#print(ys, n)
ans = 0
for i in range(n):
    x0 = 0
    x1 = 0
    for y in ys:
        #print(y,i,len(y))
        if i < len(y):
            if y[i] == "1":
                x1 += 1
            else:
                x0 +=1
        else:
            x0 += 1
    #print(x1,x0)
    ans += x1 * x0 * (2**(i))
    ans %= 10**9 + 7
print(ans)


### FIXED CODE ###

words = lambda t : list(map(t, input().split()))
n = int(input())
xs = words(int)

ys = [0]*60
for x in xs:
    for i in range(60):
        if x == 0:
            continue
        ys[i] += x & 1
        x = x >> 1

ans = 0

for i,yi in enumerate(ys):
    ans += 2**(i) * yi * (n-yi)
    ans %= 10**9 + 7
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
mod = 10**9 + 7

ans = 0
G = []
for s in S:
    G.append(s)
    ans += 1
    ans %= mod

    tmp = []
    for g in G:
        if s not in g:
            ans += 1
            ans %= mod
            tmp.append(g+s)
    G += tmp
print(ans)


### FIXED CODE ###

N=int(input())
S=input()
ans=1

for s in set(S):
    ans*=S.count(s)+1

print((ans-1)%1000000007)
### BUGGY CODE ###

# A - Darker and Darker
import numpy as np

H,W = map(int,input().split())
h,w = np.arange(H,dtype=int),np.arange(W,dtype=int)
A = [list(input()) for _ in range(H)]

queue = []
new_queue = []

for i in h:
    for j in w:
        if A[i][j]=='#':
            queue.append((i,j))
            
def darker(i,j):
    if (i in h) and (j in w) and A[i][j]=='.':
        A[i][j]='#'
        new_queue.append((int(i),int(j)))

ans = 0

while True:
    new_queue = []
    for i,j in queue:
        darker(i-1,j)
        darker(i+1,j)
        darker(i,j-1)
        darker(i,j+1)
    if new_queue==[]:
        break
    ans += 1
    queue = new_queue 

print(ans)

### FIXED CODE ###

# A - Darker and Darker
from collections import deque

H,W = map(int,input().split())
B = [[-1] * W for _ in range(H)]

queue = deque([])

for i in range(H):
    A = input()
    for j in range(W):
        if A[j]=='#':
            B[i][j] = 0
            queue.append((i,j))

ans = 0

while queue:
    I,J = queue.popleft()
    for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):
        i,j = I+di,J+dj
        if 0<=i<H and 0<=j<W:
            if B[i][j]<0:
                B[i][j] = B[I][J]+1
                ans = max(ans,B[i][j])
                queue.append((i,j))

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

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

# print(N, l)
# Pi < Pj
result = []
r = False
for i in range(1, N+1):
    count = 0
    for j in range(0, i):
        if P[i - 1] <= P[j]:
            count += 1
    if count >= i:
        result.append(i)

print(len(set(result)))


### FIXED CODE ###

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

result = 0
m = P[0]
for i in range(N):
    if P[i] <= m:
        result += 1
        m = P[i]
print(result)
### BUGGY CODE ###

from math import sqrt
cash = {}
def isprime(n):
    if n in cash:
        return cash[n]
    if n == 1:
        return 0
    if n == 2:
        return 1
    if n % 2 == 0:
        return 0
    for i in range(2,int(sqrt(n)+1)):
        if n % i == 0:
            return 0
    cash[n] = 1
    return 1

from sys import stdin
h = {}
for i in stdin:
    i = int(i)
    c = sum(isprime(n) for n in range(2,i+1))
    print(c)

### FIXED CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n)
    if n % 2 == 0:
      l = [0, 1] + [1, 0] * (int(n/2) - 1)
    else:
      l = [0, 1] + [1, 0] * (int(n/2) - 1) + [1]
    c = 3
    while c < mx:
        for k in range(c*2, n+1, c):
            l[k-1] = 0
        c = l[(c+1):].index(1) + c +2
        while c % 2 == 0:
            c = l[(c+1):].index(1) + c +2
    return l
t = cntPrime(1000000)
for n in stdin:
    n = int(n)
    print(sum(t[:n]))
### BUGGY CODE ###

s = input()
num = len(s)
l = []
from collections import deque
l = deque(l)   # deque オブジェクトを取得

for _ in range(1, 20190000):
    if _%2019 == 0:
        l.append(str(_))
l = set(l)
#print(l)

def aaa(s, num):
    x = 0
    for i in range(4,num+1):
        for j in range(num - i + 1):
            if s[j:j+i] in l:
                x += 1
    print(x)

aaa(s, num)

### FIXED CODE ###

s = input()[::-1]

cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

for i in s:
    tmp += int(i) * d
    cnts[tmp % 2019] += 1
    d = d * 10 % 2019 # 桁数が大きくなりすぎる → 10と2019が素だから可能

ans = 0
for cnt in cnts:
    ans += (cnt - 1) * cnt // 2

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

n=int(input())
l=list(map(int,input().split()))
dic={}
ans=0
for i in range(n):
    a=i-l[i]
    if a in dic.keys():
       dic[a].add(i)
    else:
       dic[a]={i}
for i in range(n):
  a=i+l[i]
  if a in dic.keys():
    s=dic[a]
  else:
    continue
  k=0
  for j in s:
    if i<j:
      break
    k+=1
  ans+=len(s)-k
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
l=list(map(int,input().split()))
dic={}
ans=0
for i in range(n):
    a=i-l[i]
    if a in dic.keys():
       dic[a].append(i)
    else:
       dic[a]=[i]
for i in range(n):
  a=i+l[i]
  if a in dic.keys():
    s=dic[a]
  else:
    continue
  k=bisect.bisect_right(s,i)
  ans+=(len(s)-k)
print(ans)
### BUGGY CODE ###

N,M=[int(i) for i in input().split()]
A = [int(i) for i in input().split()]
for i in range(M):
  l=A.index(max(A))
  A[l]//=2
print(sum(A))

### FIXED CODE ###

import heapq
N,M=[int(i) for i in input().split()]
A=sorted([-int(i) for i in input().split()])
for i in range(M):heapq.heappush(A,-(-heapq.heappop(A)//2))
print(-sum(A))
### BUGGY CODE ###

n = int(input())
R = []
P = []

p = float('-inf')
R.append(int(input()))
for i in range(1, n):
    r = int(input())
    if r-min(R) > p:
        p = r-min(R)
    R.append(r)

print(p)

### FIXED CODE ###

import sys

n = int(input())
r0 = int(input())
r1 = int(input())
p = r1 - r0
r = min(r0,r1)
for i in map(int, sys.stdin.readlines()):
    if p < i - r:
        p = i - r
    if r > i:
        r = i

print(p)
### BUGGY CODE ###

n=int(input())
a=(input().split())
a1={}
for i in range(n):
    a1[(a[i])]=i+1
#print(a1)    
str1=""
for i in range(n):
    a2=str(i+1)
#    print(a2)
    str1=str1 + " " + str(a1[a2])
print(str1)

### FIXED CODE ###

n=int(input())
a=(input().split())
a1={}
for i in range(n):
    a1[(a[i])]=i+1
str1=""
for i in range(n):
    print(str(a1[str(i+1)]),end=" ")
print()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
def main():
    S = input()
    l = len(S)
    dp = [[0]*(13) for _ in range(10**5+10)]
    dp[0][0] = 1
    mul = 1  
    for i in range(l):
        x = S[-(i+1)]
        if x == "?":
            for k in range(10):
                for j in range(13):
                    dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                    dp[i + 1][(mul * k + j) % 13] %= MOD
        else:
            k = int(x) # これしか選ぶ余地なし
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
        mul *= 10
    print(dp[l][5]%MOD)


if __name__ == "__main__":
    main()


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

from collections import defaultdict


def solve(row, col, d):
    x_map = defaultdict()

    for i in range(row):
        a_i = list(map(int, input().split()))
        for j in range(col):
            x_map[a_i[j]-1] = (i, j)

#    print(x_map)

    q = int(input())

    mp = 0
    for _ in range(q):
        l, r = map(int, input().split())
        for current_pos in range(l+d-1, r, d):
            cp = x_map[current_pos]
            pp = x_map[current_pos-d]
#            print("curre_pos : {0}".format(current_pos))
#            print("cp : {0}".format(cp))
#            print("pp : {0}".format(pp))
            mp += abs(cp[1] - pp[1]) + abs(cp[0] - pp[0])
        print(mp)
        mp = 0


if __name__ == '__main__':
    row, col, d = map(int, input().split())
    solve(row, col, d)


### FIXED CODE ###

from collections import defaultdict


def solve(row, col, d):
    x_map = defaultdict()

    for i in range(row):
        a_i = list(map(int, input().split()))
        for j in range(col):
            x_map[a_i[j]] = (i, j)

    q = int(input())

    dp = [0]*(row*col+1)
    for j in range(d+1, row*col+1):
        x_map_y = abs(x_map[j][0] - x_map[j-d][0])
        x_map_x = abs(x_map[j][1] - x_map[j-d][1])
        dp[j] = dp[j-d]+x_map_y+x_map_x
#        print("j {0} x_map_y : {1} x_map_x : {2} dp[j] : {3}".format(
#            j, x_map_y, x_map_x, dp[j]))

    for _ in range(q):
        l, r = map(int, input().split())
        print(dp[r]-dp[l])


if __name__ == '__main__':
    row, col, d = map(int, input().split())
    solve(row, col, d)
### BUGGY CODE ###

n = int(input())
s = input()
cou = 0
for i in range(1000):
  i = "{0:03d}".format(i)
  a,b,c = i[0],i[1],i[2]
  bit = 0
  for j in range(n):
    if bit==1:
      break
    if s[j]==a:
      for k in range(j+1,n):
        if bit==1:
          break
        if s[k]==b:
          for m in range(k+1,n):
            if s[m]==c:
              cou += 1
              bit = 1
              break
              
print(cou)

### FIXED CODE ###

n = int(input())
s = input()
cou = 0
for i in range(1000):
  i = "{0:03d}".format(i)
  t = 0
  r = 0
  while r!=n:
    if s[r]==i[t]:
      t += 1
    if t==3:
      cou += 1
      r = n-1
    r += 1            
print(cou)
### BUGGY CODE ###

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

S=[1]

for n in range (N):
    if n<K:
        S.append(A[n]*S[-1])
    else:
        S.append(A[n]*S[-1]/A[n-K])

for i in range (K+1,N+1):
    if S[i]>S[i-1]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

for i in range (K,N):
    if A[i]>A[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

def dp_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    dp=[[float("inf") for _ in range(2)] for _ in range(l+2)]
    dp[0][0]=0
    for i in range(l+1):
        for j in range(2):
            num=int(rev[i])
            num+=j
            if num<10:
                dp[i+1][0]=min(dp[i+1][0],dp[i][j]+num)
            if num>0:
                dp[i+1][1]=min(dp[i+1][1],dp[i][j]+(10-num))

    #import numpy as np
    #dp=np.array(dp)
    return(dp[l+1])

s=input()
ans=dp_solver(s)
print(ans[0])

### FIXED CODE ###

def dp_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    dp=[[float("inf") for _ in range(2)] for _ in range(l+2)]
    dp[0][0]=0
    for i in range(l+1):
        for j in range(2):
            num=int(rev[i])
            num+=j
            if num<10:
                dp[i+1][0]=min(dp[i+1][0],dp[i][j]+num)
            if num>0:
                dp[i+1][1]=min(dp[i+1][1],dp[i][j]+(10-num))

    import numpy as np
    dp=np.array(dp)
    return(dp[l+1])

def y_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    seq_flag=False
    ans=0
    next_bit=0
    kuri_cal=0
    for i in range(l-1):
        num=int(rev[i])+next_bit
        next_num=int(rev[i+1])
        if not seq_flag:
            if (num<5) or (num==5 and next_num<5):
                ans+=num
                next_bit=0
                kuri_cal=0
                continue
            seq_s=i
            seq_flag=True
            kuri_cal=10-num
            next_bit+=1
            continue
        #print(kuri_cal)
        if num<5:
            ans+=(kuri_cal+num)
            kuri_cal=0
            next_bit=0
            seq_flag=False
        elif num>5:
            kuri_cal+=10-num
        else:
            if next_num<5:
                ans+=(kuri_cal+num)
                next_bit=0
                kuri_cal=0
                seq_flag=False
            else:
                kuri_cal+=10-num
    last=int(tmp[0])+next_bit
    ans+=kuri_cal+min(last,11-last)
    return ans

n=input()
ans=y_solver(n)
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))

ans=0
bc_count=[0]*(n+1)
def check(list_count,i):
    ok=n
    ng=-1
    B=b[i]
    while ok-ng>1:
        mid=(ok+ng)//2
        if list_count[mid]>B:
            ok=mid
        else:
            ng=mid
    bc_count[i+1]=n-ok+bc_count[i]
    #print(i,ok)

for i in range(n):
    check(c,i)

bc_max=bc_count[-1]
for i in range(n):

    ind=0
    while ind<n:
        if a[i]<b[ind]:
            ans=ans+bc_max-bc_count[ind]
            break
        ind+=1

print(ans)#,bc_count)
#print(a,b,c,sep='\n')

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=sorted(list(map(int,input().split())))
b=list(map(int,input().split()))
c=sorted(list(map(int,input().split())))

ans=0
def ab_check(list_count,i):
    ok=-1
    ng=n
    B=b[i]
    while ng-ok>1:
        mid=(ok+ng)//2
        if list_count[mid]<B:
            ok=mid
        else:
            ng=mid
    #print(ok+1,'A')
    return ok+1

def bc_check(list_count,i):
    ok=n
    ng=-1
    B=b[i]
    while ok-ng>1:
        mid=(ok+ng)//2
        if list_count[mid]>B:
            ok=mid
        else:
            ng=mid
    #print(n-ok,'B')
    return n-ok
    #print(i,ok)

for i in range(n):
    ans+=ab_check(a,i)*bc_check(c,i)
print(ans)
#print(a,c,sep='\n')
### BUGGY CODE ###

from numpy import zeros

def main():
    R, C, K, *RCV = map(int, open(0).read().split())

    V = zeros((R + 1, C + 1), int)
    for r, c, v in zip(*[iter(RCV)] * 3):
        V[r][c] = v

    dp = zeros((R + 1, C + 1, 4), int)
    for i in range(1, R + 1):
        for j in range(1, C + 1):

            vij = V[i][j]

            for k in range(4):
                dp[i][j][k] = max(
                    dp[i][j - 1][k],
                    dp[i - 1][j][3]
                )
            for k in reversed(range(1, 4)):
                dp[i][j][k] = max(
                    dp[i][j][k],
                    vij + dp[i][j][k - 1]
                )

    print(dp[R][C][3])

main()

### FIXED CODE ###

from numpy import zeros, int64
from numba import njit

R, C, K, *RCV = map(int64, open(0).read().split())
V = zeros((R + 1, C + 1), int64)
for r, c, v in zip(*[iter(RCV)] * 3):
    V[r][c] = v

@njit
def main():
    dp = zeros((R + 1, C + 1, 4), int64)
    for i in range(1, R + 1):
        for j in range(1, C + 1):

            vij = V[i][j]

            for k in range(4):
                dp[i][j][k] = max(
                    dp[i][j - 1][k],
                    dp[i - 1][j][3]
                )
            for k in range(3, 0, -1):
                dp[i][j][k] = max(
                    dp[i][j][k],
                    vij + dp[i][j][k - 1]
                )

    print(dp[R][C][3])

main()
### BUGGY CODE ###

class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

    def find(self, x):
        if self.par.get(x, x) == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

N, K, L = [int(_) for _ in input().split()]

Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = [[0] * N for _ in range(N)]
for i in range(1, N + 1):
    memo[Road.find(i) - 1][Railway.find(i) - 1] += 1
print(' '.join(str(memo[Road.find(i) - 1][Railway.find(i) - 1]) for i in range(1, N + 1)))


### FIXED CODE ###

class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

    def find(self, x):
        if self.par.get(x, x) == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

N, K, L = [int(_) for _ in input().split()]

Road = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    Road.unite(p, q)
Railway = UFT()
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    Railway.unite(r, s)
memo = {}
for i in range(1, N + 1):
    memo[Road.find(i), Railway.find(i)] = memo.get((Road.find(i), Railway.find(i)), 0) + 1
print(' '.join(str(memo[Road.find(i), Railway.find(i)]) for i in range(1, N + 1)))
### BUGGY CODE ###

def solve():
    n = int(input())
    A = map(int, input().split())
    W = [0] * (n + 1)
    for a_i in A:
        W[a_i] = max(W[:a_i]) + a_i
    ans = n * (n + 1) // 2 - max(W)
    print(ans)

solve()


### FIXED CODE ###

def solve():
    n = int(input())
    dp = [0] * (n + 1)
    
    def update(i, x):
        while i <= n:
            if dp[i] < x:
                dp[i] = x
            i += i & -i
    
    def get_sum(i):
        s = 0
        while i > 0:
            t = dp[i]
            if s < t:
                s = t
            i -= i & -i
        return s
    
    A = map(int, input().split())
    
    for a_i in A:
        update(a_i, get_sum(a_i - 1) + a_i)
    
    ans = n * (n + 1) // 2 - get_sum(n)
    print(ans)

solve()
### BUGGY CODE ###

l, r = map(int, input().split())
ans = 2020
for i in range(l,r + 1):
    for j in range(i+1,r + 1):
        if (i * j) % 2019 <= ans:
            ans = min(ans, (i * j) % 2019)
print(ans)



    #print(i)

### FIXED CODE ###

l, r = map(int, input().split())
# 2019
if r - l >= 2019:
	print(0)

# この数の中に2019が含まれている．
# 2019 * 2019 - 2019 

else:
	ans = 10000
	for i in range(l, r + 1):
		for j in range(i + 1, r + 1):
			ans = min(ans, (i * j) % 2019)
	print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(0,N):
  
  for j in range(0,i):
    
    ans = ans + (A[i] * A[j])%(10**9+7)

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

### FIXED CODE ###

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

from sys import stdin
n = int(stdin.readline())
nums = list(map(int, stdin.readline().split()))

# let dp[i][j]: maximum sum of j elements chosen from the first i elements where no two are adjacent.

# dp[i][j] = max(dp[i-2][j-1] + nums[i], dp[i-1][j])
dp = [[0]*(n//2 + 1) for i in range(n+1)]

for i in range(1, n+1):
    dp[i][0] = 0

# for j in range(1, n//2 + 1):
#     dp[1][j] = nums[0]
dp[1][1] = nums[0]

for i in range(1, n+1):
    for j in range(1, i//2 + 1):
        dp[i][j] = max(nums[i-1] + (dp[i-2][j-1] if i>1 and j>0 else 0), dp[i-1][j] if i>0 else 0)

print(dp[n][n//2])
# print(dp)


### FIXED CODE ###

from sys import stdin
n = int(stdin.readline())
nums = list(map(int, stdin.readline().split()))

# Gives TLE
def naive_2D_dp(n, nums):
    # let dp[i][j]: maximum sum of j elements chosen from the first i elements where no two are adjacent.

    # dp[i][j] = max(dp[i-2][j-1] + nums[i], dp[i-1][j]); maximum between selecting the ith element and not selecting it. If we select, we have to use dp[i-2][j-1] to prevent adjacent.

    dp = [[0]*(n//2 + 1) for i in range(n+1)]

    # sum of 0 to select 0 elements
    for i in range(1, n+1):
        dp[i][0] = 0

    # to select one out of one.
    dp[1][1] = nums[0]

    for i in range(1, n+1):
        for j in range(1, i//2 + 1):
            dp[i][j] = max(nums[i-1] + (dp[i-2][j-1] if i>1 and j>0 else 0), dp[i-1][j] if i>0 else 0)

    print(dp[n][n//2])


# Source: https://icode54.blogspot.com/p/dp-1-atcoder-beginner-contest-162.html
def oneD_dp(n, nums):
    # let dp[i] be the maximum sum after picking i/2 elements. Two cases: i is odd, i is even. In both we choose the max from selecting i, and not selecting i.


    # Case 1) i is even (pick exactly i/2 elements): dp[i] = max(dp[i-2] + nums[i], odd indices sum). 
    # 1 2 3 4 5 6. If you pick 6 (i) you check the max of (i-2). If you don't pick 6, to pick i/2 elements you ave to pick the odd indices : 1, 3, 5.

    # Case 2) i is odd (i/2 is same as (i-1)/2 if we don't pick): dp[i] = max(dp[i-2] + nums[i], dp[i-1])

    # odd indices prefix sum needed for even case.
    oddpref = [0]*(n+1)
    oddpref[1] = nums[0]

    for i in range(3, n+1, 2):
        if i%2:
            oddpref[i] += oddpref[i-2] + nums[i-1]
    
    dp = [0]*(n+1)
    dp[0] = 0
    dp[1] = 0
    for i in range(2, n+1):
        if i%2 == 0:
            dp[i] = max(dp[i-2] + nums[i-1], oddpref[i-1])
        else:
            dp[i] = max(dp[i-2] + nums[i-1], dp[i-1])
    print(dp[n])

oneD_dp(n, nums)