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

def func1(x, y, z, a):
  if x == y:
    z.append(a)
    return 1 
  return 0

def func2(x, y, z, a):
  if x==y and z==a:
    return 1
  return 0

  
N = int(input())
S = input()
r, g, b, rgb, equal = 0, 0, 0, 0, 0
r0, g0, b0 = [], [], []

for i in range(N):
  r += func1(S[i], 'R', r0, i)
  g += func1(S[i], 'G', g0, i)
  b += func1(S[i], 'B', b0, i)
    
rgb = r * g * b

# Rが最小
for i in r0:
  for j in range(i+1, N-1):
    k = 2 * j - i
    if k <= N-1:
      equal += func2(S[j], 'G', S[k], 'B')
      equal += func2(S[j], 'B', S[k], 'G')

# Gが最小
for i in g0:
  for j in range(i+1, N-1):
    k = 2 * j - i
    if k <= N-1:
      equal += func2(S[j], 'R', S[k], 'B')
      equal += func2(S[j], 'B', S[k], 'R')

# Bが最小
for i in b0:
  for j in range(i+1, N-1):
    k = 2 * j - i
    if k <= N-1:
      equal += func2(S[j], 'R', S[k], 'G')
      equal += func2(S[j], 'G', S[k], 'R')

print(rgb - equal)

### FIXED CODE ###

def func1(x, y, z, a):
  if x == y:
    z.append(a)
    return 1 
  return 0

def func2(x, y):
  if x==y:
    return 1
  return 0

def func3(x, y, z, a):
  l = 0
  for i in x:
    for j in y:
      k = 2 * j - i
      if k <= N-1 and i < j:
        l += func2(z[k], a)
  return l

  
N = int(input())
S = input()
r, g, b, rgb, equal = 0, 0, 0, 0, 0
r0, g0, b0 = [], [], []

for i in range(N):
  r += func1(S[i], 'R', r0, i)
  g += func1(S[i], 'G', g0, i)
  b += func1(S[i], 'B', b0, i)

rgb = r * g * b

# R<G<B
equal += func3(r0, g0, S, 'B')
# R<B<G
equal += func3(r0, b0, S, 'G')
# G<R<B
equal += func3(g0, r0, S, 'B')
# G<B<R
equal += func3(g0, b0, S, 'R')
# B<R<G
equal += func3(b0, r0, S, 'G')
# B<G<R
equal += func3(b0, g0, S, 'R')

print(rgb - equal)
### BUGGY CODE ###

N, K = map(int, input().split())
h = [0]
h[1:] = list(map(int, input().split()))
inf = 1 << 60
dp = [inf] * (N + 1)
dp[0] = 0
dp[1] = 0
for i in range(2, N + 1):
    for k in range(1, min(i, K + 1)):
        dp[i] = min(dp[i], dp[i - k] + abs(h[i - k] - h[i]))

print(dp[N])


### FIXED CODE ###

N, K = map(int, input().split())
h = [0]
h[1:] = list(map(int, input().split()))
inf = 1 << 60
dp = [inf] * (N + 1)
dp[0] = 0
dp[1] = 0
for i in range(2, N + 1):
    for k in range(1, min(i, K + 1)):
        dp[i] = min(dp[i], dp[i - k] + abs(h[i - k] - h[i]))

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

input()
a=1
for i in input().split():
  a*=int(i)
print([a,-1][a>1000000000000000000])

### FIXED CODE ###

input()
a=1
d=1000000000000000000
for i in input().split():
  a=min(a*int(i), d+1)
print([a,-1][a>d])
### BUGGY CODE ###

#!python3

import sys

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i)
        if cmd == "1":
            S[i-1] = j
        elif cmd == "2":
            s1 = set()
            for ii in range(i-1, int(j)):
                s1.add(S[ii])
            ans.append(len(s1))

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

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys

from bisect import bisect, insort_left

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.pop(bisect(s1, i)-1)
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

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

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

from sys import stdin
input = stdin.readline

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

ans_ls = []
tmp = 1

for i in range(K):
    tmp *= A[i]

ans_ls.append(tmp)

for i in range(K, N):
    tmp //= A[i - K]
    tmp *= A[i]
    ans_ls.append(tmp)

for i in range(len(ans_ls) - 1):
    if ans_ls[i + 1] <= ans_ls[i]:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

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

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

q = deque([])

for i in range(K):
    q.append(A[i])

for i in range(K, N):
    tmp = q.popleft()
    if A[i] <= tmp:
        print("No")
    else:
        print("Yes")
    q.append(A[i])
### BUGGY CODE ###

N = int(input()) 
A = list(map(int, input().split()))
flag = 1
ans = 1
for a in A:
  ans *= a


if ans > 10**18 :
  print(-1)
else:
  print(ans)

 

### FIXED CODE ###


N = int(input()) 
A = list(map(int, input().split()))
S = set(A)
if 0 in S:
  print(0)
  exit()
 
upp = 10**18
flag = 1
ans = 1
#print(A)
for a in A:
  ans *= a
  if ans > upp:
    ans = -1
    break
 
print(ans)
### BUGGY CODE ###

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


import sys

if K > N**(1/2):
    A = [N]*N
    print(' '.join(map(str, A)))
    sys.exit()
    

import numpy as np
A = np.array(A, dtype=int)
lenA = len(A)
for i in range(K):
    B = np.zeros(lenA, dtype=int)
#    print(B)
    for j in range(lenA):
        num = A[j]
#        print(j, num)
        B[max(0, j - num): min(lenA, j + num + 1)] += 1
#        print(j, B)
    if np.all(A == B):
#        print('same')
        break
    else:
        A = B
#print(i+1)
print(' '.join(map(str, A)))

### FIXED CODE ###

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

lenA = len(A)
for i in range(K):
    B = [0 for _ in range(lenA)]
#    print(B)
    for j in range(lenA):
        num = A[j]
#        print(j, num)
        if j - num >= 0:
            B[max(0, j - num)] += 1
        else:
            B[0] += 1
        if j + num + 1 < lenA:
            B[min(lenA, j + num + 1)] -= 1
#        print(j, B)
    for i in range(1, lenA):
        B[i] = B[i-1] + B[i]
    if all([a == b for a, b in zip(A,B)]):
#        print('same')
        break
    else:
        A = B
#print(i+1)
print(' '.join(map(str, A)))
### BUGGY CODE ###

N=int(input())
S=list(input())

ans=0

for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if j-i != k-j and S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                ans += 1

print(ans)

### FIXED CODE ###

N=int(input())
S=input()

ans = S.count("R")*S.count("G")*S.count("B")

tmp=0

for i in range(N):
  for j in range(i,N):
    if j-i+j < N:
      if S[i]!=S[j] and S[j]!=S[j-i+j] and S[i]!=S[j-i+j]:
        tmp += 1

ans = ans - tmp
print(ans)
### BUGGY CODE ###

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

A=[]          
for i in range(N-K+1):
            A.append(sum(p[i:i+K]))
print((max(A)+K)/2)


### FIXED CODE ###

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

p_=[]
for i in range(len(p)):
  p_.append((1+p[i])/2)
 
import itertools
c=list(itertools.accumulate(p_))

ans=0
if N!=K:
  
  for i in range(0,N-K):
    s=c[i+K]-c[i]
    ans=max(ans,s)
else:
  ans=c[K-1]
print(ans)
### BUGGY CODE ###

from collections import deque

H, W = map(int, list(input().split()))
Ch, Cw = map(int, list(input().split()))
Ch -= 1
Cw -= 1
Dh, Dw = map(int, list(input().split()))
Dh -= 1
Dw -= 1
S = [list(input()) for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

seen = [[None] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
            continue
        if S[nh][nw] == '#':
            continue
        if seen[nh][nw] is not None and seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
                continue
            if S[nh][nw] == '#':
                continue
            if seen[nh][nw] is not None and seen[nh][nw] <= seen[th][tw]:
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.append([nh, nw])

if seen[Dh][Dw] is not None:
    print(seen[Dh][Dw])
else:
    print(-1)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh, Dw = map(int, input().split())
Dh -= 1
Dw -= 1
S = [input() for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '#' or seen[nh][nw] <= seen[th][tw] + 1:
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.appendleft([nh, nw])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])
### BUGGY CODE ###

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

#print(n,q)
edge=[]
for i in range(n-1):
    a = list(map(int,input().split()))
    edge.append(a)

add_list = []
for i in range(q):
    p = list(map(int,input().split()))
    add_list.append(p)

#print(edge,add_list)

ans = [0] * n
edge_list = [[] for i in range(n)]

for e in edge:
    edge_list[e[1]-1].append(e[0]-1)

add_value = [0]*n
for v in add_list:
    add_value[v[0]-1] += v[1]

#print(edge_list)
#print(add_value)


dp = [-1] * n
def get_value(i):
    if(dp[i]!=-1):
        return dp[i]
    tmp = add_value[i]
    for e in edge_list[i]:
        tmp += get_value(e)
    dp[i] = tmp
    return dp[i]

for i in range(n):
    ans[i] = get_value(i)
    #print(i,ans)

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

### FIXED CODE ###

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

#print(n,q)
edge=[]
for i in range(n-1):
    a = list(map(int,input().split()))
    edge.append(a)

add_list = []
for i in range(q):
    p = list(map(int,input().split()))
    add_list.append(p)

#print(edge,add_list)

ans = [0] * n
edge_list = [-1] * n

for e in edge:
    edge_list[e[1]-1] = e[0]-1

add_value = [0]*n
for v in add_list:
    add_value[v[0]-1] += v[1]

#print(edge_list)
#print(add_value)


dp = [-1] * n
def get_value(i):
    if(dp[i]!=-1):
        return dp[i]
    tmp = add_value[i]
    if edge_list[i] != -1:
        tmp += get_value(edge_list[i])
    dp[i] = tmp
    return dp[i]

for i in range(n):
    ans[i] = get_value(i)
    #print(i,ans)

print(' '.join(map(str,ans)))
### BUGGY CODE ###

n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
p = [0 for i in range(n+1)]
for i in range(1,n+1):
    if i in a:
        p[i] = 0
    elif i == 1:
        p[i] = 1
    elif i == 2:
        p[i] = p[1] + 1
    else:
        p[i] = p[i-1] + p[i-2]
print(p[n] % (10**9 + 7))

### FIXED CODE ###

n, m = map(int,input().split())
p = [0 for i in range(n+1)]
a = [0 for i in range(n+1)]
for i in range(m):
    a[int(input())] = 1
for i in range(1,n+1):
    if a[i] == 1:
        p[i] = 0
    elif i == 1:
        p[i] = 1
    elif i == 2:
        p[i] = p[1] + 1
    else:
        p[i] = p[i-1] + p[i-2]
print(p[n] % (10**9 + 7))
### BUGGY CODE ###

n = int(input())
s = input()

dp = [[0]*10 for _ in range(10)]

result = []
for i in range(n-2):
    for j in range(i+1,n-1):
        if dp[int(s[i])][int(s[j])]==0:
            tem = "".join(set(s[j+1:]))
            for k in range(len(tem)):
                result.append(s[i]+s[j]+tem[k])
            dp[int(s[i])][int(s[j])]=1

ans = set(result)
print(len(ans))

### FIXED CODE ###

n = int(input())
s = input()

dp = [[0]*10 for _ in range(10)]

count = [0]*10

result = []

for i in range(n-2):
    if count[int(s[i])]==0:
        for j in range(i+1,n-1):
            if dp[int(s[i])][int(s[j])]==0:
                tem = "".join(set(s[j+1:]))
                for k in range(len(tem)):
                    result.append(s[i]+s[j]+tem[k])
                dp[int(s[i])][int(s[j])]=1
        count[int(s[i])]=1

ans = set(result)
print(len(ans))
### BUGGY CODE ###

s=input()
a=0
m={}
for i in range(len(s)):
  b=int(s[len(s)-1-i])*10**i+a
  b=b%2019
  a=b
  if b in m:
    m[b]+=1
  else:
    m[b]=1
if 0 in m:
  sum=m[0]
else:
  sum=0
for i in m:
  sum+=m[i]*(m[i]-1)/2
print(int(sum))



### FIXED CODE ###

s=input()
a=0
m={}
d=1
for i in range(len(s)):
  b=int(s[len(s)-1-i])*d+a
  b=b%2019
  a=b
  d=d*10%2019
  if b in m:
    m[b]+=1
  else:
    m[b]=1
if 0 in m:
  sum=m[0]
else:
  sum=0
for i in m:
  sum+=m[i]*(m[i]-1)/2
print(int(sum))
### BUGGY CODE ###

mod = 10 ** 9 + 7

def naive_main(nums):
    n = len(nums)
    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            ans += nums[i] ^ nums[j]
    return ans

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

# s

"""
0 0 0 1
0 0 1 0
0 0 1 0
0 1 0 0
1 0 0 0

4, 4, 6, 4

32 16 12 4
"""

max_len = len(bin(max(nums))) - 2

counter = [0 for _ in range(max_len)]
for i in range(n):
    ss = bin(nums[i])[2:]
    ss = "0" * (max_len - len(ss)) + ss
    for j in range(len(ss)):
        if ss[j] == "1":
            counter[j] += 1

# print(n)
# print(counter)
ans = 0
for i in range(max_len):
    c = counter[max_len - 1 - i]
    ans += (c * (n - c) * (2 ** i)) % mod

print(int(ans) % mod)
#print(naive_main(nums))



### FIXED CODE ###

mod = 10 ** 9 + 7

def naive_main(nums):
    n = len(nums)
    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            ans += nums[i] ^ nums[j]
    return ans

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

# s

"""
0 0 0 1
0 0 1 0
0 0 1 0
0 1 0 0
1 0 0 0

4, 4, 6, 4

32 16 12 4
"""

max_len = len(bin(max(nums))) - 2

counter = [0 for _ in range(max_len)]
for i in range(n):
    ss = bin(nums[i])[2:]
    ss = "0" * (max_len - len(ss)) + ss
    for j in range(len(ss)):
        if ss[j] == "1":
            counter[j] += 1

# print(n)
# print(counter)
ans = 0
for i in range(max_len):
    c = counter[max_len - 1 - i]
    ans += (c * (n - c) * (2 ** i)) % mod

print(int(ans) % mod)
#print(naive_main(nums))
### BUGGY CODE ###

import bisect

input()
A=[int(i) for i in input().split()]
B=sorted([int(i) for i in input().split()])
C=sorted([int(i) for i in input().split()])

ans=0
for a in A:
  for b in B[bisect.bisect_right(B,a):]:
    ans+=len(C[bisect.bisect_right(C,b):])

print(ans)

### FIXED CODE ###

import bisect

N=int(input())
A=sorted([int(i) for i in input().split()])
B=sorted([int(i) for i in input().split()])
C=sorted([int(i) for i in input().split()])

ans=0
for b in B:
  ans+=bisect.bisect_left(A,b)*(N-bisect.bisect_right(C,b))

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

n, m = map(int, input().split())
arr = list(map(int, input().split()))
for _ in range(m):
    _max = max(arr)
    i = arr.index(_max)
    arr[i] = _max // 2
print(sum(arr))

### FIXED CODE ###

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())), reverse=True)

b = arr[0] // 2
i = 0
while True:
    if m == 0:
        break
    if b <= arr[i]:
        arr[i] = arr[i] // 2
        m -= 1
    else:
        arr = sorted(arr, reverse=True)
        i = 0
        b = arr[0] // 2
        continue
    if i < n-1:
        i += 1
    else:
        i = 0

print(sum(arr))
### BUGGY CODE ###

import heapq
N,M=map(int,input().split())
A=sorted(list(map(int,input().split())))
lst=[[0,0] for _ in range(M)]
h=[]
for i in range(M):
  lst[i]=list(map(int,input().split()))
  heapq.heappush(h,[-1*lst[i][1],lst[i][0]])

for i in range(M):
  v=heapq.heappop(h)
  v1,v2=-1*v[0],v[1]
  if A[0]>v1:
    break
  else:
    while v2!=0 and A[0]<v1:
      val=A.pop(0)
      heapq.heappush(A,v1)
      v2-=1 
print(sum(A))

### FIXED CODE ###

import heapq
import sys
N,M=map(int,input().split())
A=sorted(list(map(int,input().split())))
lst=[[0,0] for _ in range(M)]
h=[]
for i in range(M):
  lst[i]=list(map(int,input().split()))
  heapq.heappush(h,[-1*lst[i][1],lst[i][0]])
i=0
while len(h)!=0:
    v=heapq.heappop(h)
    v1,v2=-1*v[0],v[1]
    while i<=N-1 and A[i]<v1 and v2!=0:
        A[i]=v1
        i+=1
        v2-=1
    if v2>=1:
        print(sum(A))
        sys.exit()
print(sum(A))
### BUGGY CODE ###

from operator import itemgetter, attrgetter
#input
n = int(input())
H = [list(map(int, input().split())) for _ in range(n)]
C = sorted(H, key = itemgetter(0), reverse = True)
A = sorted(H, key = itemgetter(1), reverse = True)

ans_c = 0
ans_a = 0
turn = 0

while C != [] and A != []:
    if turn % 2 == 0: #chokudai 
        if C[0][0] - A[0][0] >= A[0][1] - C[0][1]:
            chokudai = C.pop(0)
            ans_c += chokudai[0]
            A = sorted(C, key = itemgetter(1), reverse = True)
        else:
            chokudai = A.pop(0)
            ans_c += chokudai[0]
            C = sorted(A, key = itemgetter(0), reverse = True)
    else: #aoki
        if A[0][1] - C[0][1] >= C[0][0] - A[0][0]:
            aoki = A.pop(0)
            ans_a += aoki[1]
            C = sorted(A, key = itemgetter(1), reverse = True)
        else:
            aoki = C.pop(0)
            ans_a += aoki[1]
            A = sorted(C, key = itemgetter(1), reverse = True)
    turn += 1

print(ans_c - ans_a)


### FIXED CODE ###

#input
n = int(input())
H = []
for _ in range(n):
    a, b = map(int, input().split())
    H.append([a + b, a, b])

H = sorted(H, reverse = True)
sum_c = 0
sum_a = 0

for i in range(n):
    if i % 2 == 0:
        sum_c += H[i][1]
    else:
        sum_a += H[i][2]

ans = sum_c - sum_a
print(ans)
### BUGGY CODE ###

N = int(input())
a = 0
i = 1
while N//i != 0:
    if N//(i*10) != 0:
        a += i*10 - i
        i = i*100
    else:
        a = N - i +1
print(a)

### FIXED CODE ###

N = int(input())
a = 0
i = 1
while N//i != 0:
    if N//(i*10) != 0:
        a += i*10 - i
        i = i*100
    else:
        a += N - i +1
        i = i*100
print(a)
### BUGGY CODE ###

s = input()

times = 0
while 'ABC' in s:
  times += 1
  s = s.replace('ABC', 'BCA', 1)
print(times)


### FIXED CODE ###

import re

s = input()
s = s.replace('BC', 'D')
ss = [c for c in re.split('[BC]', s) if c != '']

sum = 0
for s in ss:
  na = 0
  for c in s:
    if c == 'A':
      na += 1
    else:
      sum += na

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

N = int(input())
A = list(map(int,input().split()))
ans = 1
for i in range(N):
  ans *= A[i]
if ans > 10 ** 18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
A = sorted(A)
for i in range(N):
  ans *= A[i]
  if ans > 10 ** 18:
    ans = -1
    break
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def dp(H, memo):
    if H in memo:
        return memo[H]
    if H <= 0:
        return 0
    res = min(dp(H - a, memo) + b for a, b in AB)
    memo[H] = res
    return res

H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
memo = {}
print(dp(H, memo))

### FIXED CODE ###

H, N = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(N)]
dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H + 1):
    for a, b in AB:
        h_new = min(h + a, H)
        dp[h_new] = min(dp[h] + b, dp[h_new])
print(dp[-1])
### BUGGY CODE ###

n = int(input())
a = [int(s) for s in input().split()]

total=0

for i in range(n-1):
  for j in range(n-i-1):
    total=total+a[i]*a[i+j+1]%1000000007
    
print(total% 1000000007)


### FIXED CODE ###

n = int(input())
a = [int(s) for s in input().split()]
s=sum(a)

total=0

for i in range(n-1):
  s=s-a[i]
  total=total+a[i]*s%1000000007
  
print(total%1000000007)
### BUGGY CODE ###

n, a, b = (int(i) for i in input().split())
s=0
h=0
for i in range(1,n):
  j=0
  s=0
  while j<4:
    s += i%10
    i = i/10
  if s>=a and s<=b:
    h += s
    

print(h)

### FIXED CODE ###

n, a, b = (int(i) for i in input().split())
s=0
h=0
f=0
for i in range(1,n+1):
  j=0
  s=0
  f=i
  while j<5:
    s += i%10
    i = int(i/10)
    j=j+1
    #if i==0:
     # break
  if s>=a and s<=b:
    h = h + f
    
print(h)
### BUGGY CODE ###

n=int(input())
a=1
for i in range(1,n+1):
	a=a*i
print(a%(1000000000+7))

### FIXED CODE ###

n=int(input())
a=1
for i in range(1,n+1):
	a=a%(1000000000+7)*i%(1000000000+7)
print(a%(1000000000+7))
### BUGGY CODE ###

import sys

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

a, v = map(int, readline().split())
b, w = map(int, readline().split())
t = int(readline())

d = abs(b - a)
flg = 0

for i in range(t):
    d = d - v + w
    if d <= 0:
        flg = 1

if flg == 1:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

import sys

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

a, v = map(int, readline().split())
b, w = map(int, readline().split())
t = int(readline())

d = abs(b - a)

d = d - (v - w)*t
if d <= 0:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

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

import numpy as np
for i in range(M):
  A[np.argmax(np.array(A))] //= 2
print(sum(A))


### FIXED CODE ###

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

import heapq
a = [-1*i for i in a]
heapq.heapify(a)
for i in range(M):
    b = heapq.heappop(a)
    b = (-1*b)//2
    heapq.heappush(a, -1*b)
print(-1*sum(a))
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = 1e+6
for n in range(N):
    score = len([x for x in S[:n] if x == 'W']) + len([x for x in S[n + 1:] if x == 'E'])
    ans = min(ans, score)
print(ans)

### FIXED CODE ###

N = int(input())
S =input()
wn = [0] * (N + 1)
en = [0] * (N + 1)
for i in range(1, N + 1):
    if S[i - 1] == 'W':
        wn[i] = wn[i - 1] + 1
        en[i] = en[i - 1]
    else:
        wn[i] = wn[i - 1]
        en[i] = en[i - 1] + 1
ans = [wn[i] + en[N] - en[i + 1] for i in range(N)]
print(min(ans))
### BUGGY CODE ###

n = int(input())
s = str(input())

r = s.count('R')
g = s.count('G')
b = s.count('B')
all_count = r*g*b

reduce = 0
for i in range(1, n-2+1):
    for j in range(i+1, n-1+1):
        k = 2*j -i
        if k > n: continue
        if s[i-1] != s[j-1] and s[i-1] != s[k-1] and s[j-1] != s[k-1]:
            reduce += 1
print(all_count - reduce)

### FIXED CODE ###

n = int(input())
s = str(input())

r = s.count('R')
g = s.count('G')
b = s.count('B')
all_count = r*g*b

reduce = 0
for i in range(1, n-2+1):
    for j in range(i+1, (n+i)//2+1):
        k = 2*j -i
        if k > n: continue
        if s[i-1] != s[j-1] and s[i-1] != s[k-1] and s[j-1] != s[k-1]:
            reduce += 1
print(all_count - reduce)