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

import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product

# input = sys.stdin.readline

def ff(N):
#     print("call ff{0}".format(N))
    if N > 100:
        n = int(np.sqrt(20))+5
    else:
        n = N
    cnt = 0
    for x in range(1, n+1):
        x2 = x**2
        for y in range(1, n+1):
            y2 = y**2
            xy = x * y
            tt = x2 + y2 + xy
            if tt > N:
                break
            for z in range(1, n+1):
                num = tt + z**2 + x*z + y*z
                if N == num:
                    cnt += 1
#                elif N < num:
#                    break
    return(cnt)    
    
N = int(input())    
n = int(np.sqrt(20))+1
for i in range(1, N+1):
#     ff(i)
     print(ff(i))













### FIXED CODE ###

import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product

# input = sys.stdin.readline

N = int(input())
n_np = np.zeros(105**3)
for i in range(1, 105):
    for j in range(1, 105):
        for k in range(1, 105):
            idx = i**2 + j**2 + k **2 + i*j + i*k + j*k
            n_np[idx-1] += 1
for i in range(N):
    print(int(n_np[i]))
### BUGGY CODE ###

N = int(input())
S = input()
S = list(S)
count = 0
for i in range(N):
  for j in range(i+1, N):
    if S[i] == S[j]:
      continue
    for k in range(j+1, N):
      if S[i] == S[j] or S[j] == S[k] or S[i] == S[k]:
        continue
      if j-i == k-j:
          continue
      count += 1
print(count)

### FIXED CODE ###

n=int(input());s=[*input()];count=0
count=s.count('R')*s.count('G')*s.count('B')
for i in range(n+1):
  for j in range(i,n+1):
    k=2*j-i
    if k<n:
      if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k]:
        count-=1
print(count)
### BUGGY CODE ###

N=input()
H=map(int, raw_input().split())

dp=[ float("inf") for i in range(N) ] 
dp[0]=0

for k in range(N-1):
	for i in range(N,-1,-1):
		if i+2<N:dp[i+2]=min(dp[i+2], dp[i]+ abs( H[i]-H[i+2] )  )
		if i+1<N: dp[i+1]=min(dp[i+1], dp[i]+ abs( H[i]-H[i+1] )  )

print dp[N-1]


### FIXED CODE ###

N=input()
H=map(int, raw_input().split())

dp=[ float("inf") for i in range(N) ] 
dp[0]=0

for i in range(N-1):
	if i+2<N:dp[i+2]=min(dp[i+2], dp[i]+ abs( H[i]-H[i+2] )  )
	if i+1<N: dp[i+1]=min(dp[i+1], dp[i]+ abs( H[i]-H[i+1] )  )

print dp[N-1]
### BUGGY CODE ###

n = int(input())
p = 1
for i in range(1,n+1):
    p*=i

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


### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans=ans*i%(1e9+7)

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

n=int(input())
ss=[input() for _ in range(n)]
ans=0
for i,s in enumerate(ss):
    for s_ in ss[i+1:]:
        if sorted(s)==sorted(s_):
            ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
d=dict()
a=0
for _ in range(n):
    s=''.join(sorted(input()))
    if s in d:
        a+=d[s]
        d[s]+=1
    else:
        d[s]=1
print(a)
### BUGGY CODE ###

n = int(input())
s = input()
M = 10**9 + 7

dp = [[None] * n for _ in range(n)]
def dfs(zk, i=0):
    if dp[zk][i] is not None:
        return dp[zk][i]

    if i == n - 1:
        dp[zk][i] = 1
        return 1

    zj = n - i - zk - 1
    cnt = 0

    if s[i] == "<":
        for v in range(zk):
            cnt += dfs(v, i + 1)
    else:
        for v in range(zj):
            cnt += dfs(zk + v, i + 1)
    dp[zk][i] = cnt
    return cnt

def mod(v):
    if v >= M:
        return v % M
    return v

def cumsum(array):
    array = array[:]
    for i in range(len(array) - 1):
        array[i + 1] = mod(array[i + 1] + array[i])
    return array + [0]

for i in reversed(range(n)):
    for zk in range(n):
        if i == n - 1:
            dp[i][zk] = 1
            continue

        zj = n - i - zk - 1
        cnt = 0

        if s[i] == "<":
            for v in range(zk):
                # cnt = mod(cnt + dp[i + 1][v])
                cnt = cs[v]
        else:
            for v in range(zj):
                # cnt = mod(cnt + dp[i + 1][zk + v])
                cnt = cs[zk + zj - 1] - cs[zk - 1]
        dp[i][zk] = cnt
    cs = cumsum(dp[i])

# for i in range(n):
#     print(dfs(i))
# print(sum(dfs(i) for i in range(n - 1)) % M)
print(sum(dp[0]) % M)


### FIXED CODE ###

n = int(input())
s = input()
M = 10**9 + 7

def mod(v):
    if v >= M:
        return v % M
    return v


dp = [[1] * n + [0] for _ in range(2)]
s = [v == "<" for v in s]
for i in reversed(range(n - 1)):
    for j in range(n - 1):
        dp[1][j + 1] = dp[1][j + 1] + dp[1][j]
        dp[0][j] = dp[1][j]
    dp[0][-2] = dp[1][-2]

    for zk in range(n - i):
        cnt = 0

        if s[i]:
            cnt = dp[0][zk - 1]
        else:
            zj = n - i - zk - 1
            cnt = dp[0][zk + zj - 1] - dp[0][zk - 1]
        dp[1][zk] = mod(cnt)

print(sum(dp[1]) % M)
### BUGGY CODE ###

import sys
from collections import Counter

read = sys.stdin.buffer.read


def divisors(n):
    lower = []
    upper = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            lower.append(i)
            if i != n // i:
                upper.append(n // i)

    lower.extend(reversed(upper))
    return lower


def main():
    N, *A = map(int, read().split())
    A.sort()
    C = Counter(A)
    A_set = set(A)

    ans = 0
    for a in A_set:
        if C[a] != 1:
            continue
        D = divisors(a)
        if all(d not in A_set for d in D[:-1]):
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())
    A.sort()

    M = 10 ** 6
    B = [True] * (M + 1)
    B[0] = False
    ans = 0
    for i in range(N):
        if not B[A[i]]:
            continue
        if i < N - 1 and A[i + 1] == A[i]:
            B[A[i]] = False
        else:
            ans += 1
        for n in range(2 * A[i], M + 1, A[i]):
            B[n] = False

    print(ans)
    return


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

import sys
sys.setrecursionlimit(2147483647)
INF=10**10
MOD=10**9+7
input=sys.stdin.readline

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

#初期値が0の辞書
from collections import defaultdict
lrd = defaultdict(lambda: []) 

lr=defaultdict(lambda: 0) 

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x)
    for llrrdd in lrd[x]:
        #print(lrd,item,x)
        item=llrrdd[0]
        if answer[item]==INF:
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n

for i in range(n):
    if checked[i]==0:
        answer = defaultdict(lambda: INF) 
        answer[i]=1
        BFD(i)

print("Yes")


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

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

lrd=[[] for _ in range(n)]

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x,lrd[x])
    for llrrdd in lrd[x]:
        #print(llrrdd,x)
        item=llrrdd[0]
        if answer[item]=="first":
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n
answer = ["first"]*n

for i in range(n):
    if checked[i]==0:
        answer[i]=1
        BFD(i)

print("Yes")
### BUGGY CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i in input().split()]

# aとfの組み合わせはソートして逆向きが最適
# 帰納法で示す

# チームの成績x→単に成績x,メンバーiの成績→xi

# 0<=x<=a[-1]*f[0]な整数xがあったら
# 成績x以下にすることはできるか？という命題を考える

# gi=int(x/fi)は食べ物iで成績xiを出せる最大値
# 　aiがgiを超えてしまうと成績xi以下は修行しないと出せない
# 　ai<=giならその人の成績はxi以下になる
# なのでmax(ai-gi,0)は成績xi以下であるために必要な修行の回数

# よってsum=Σmax(ai-gi,0)は成績x以下を達成するのに、必要なチーム全体の総修行回数
# したってsum<=Kなら成績x以下にすることができる

# 各整数について命題はFalseかTrueを返す
# その順番は1から順にF...FT...Tとなる
# この一番左のTの整数xが求めたい最小値：チームの成績xの最小値

a.sort()
f.sort(reverse=True)

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        syugyo += max(A-int(x/F),0)
    if syugyo <= k:
        return True
    return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)
    
# 計算量は 1+2logN + N*log(2)N <= N*logN < 3.6 * 10^6 
# ぎりぎりセーフ？

### FIXED CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i in input().split()]

# aとfの組み合わせはソートして逆向きが最適
# 帰納法で示す

# チームの成績x→単に成績x,メンバーiの成績→xi

# 0<=x<=a[-1]*f[0]な整数xがあったら
# 成績x以下にすることはできるか？という命題を考える

# gi=int(x/fi)は食べ物iで成績xiを出せる最大値
# 　aiがgiを超えてしまうと成績xi以下は修行しないと出せない
# 　ai<=giならその人の成績はxi以下になる
# なのでmax(ai-gi,0)は成績xi以下であるために必要な修行の回数

# よってsum=Σmax(ai-gi,0)は成績x以下を達成するのに、必要なチーム全体の総修行回数
# したってsum<=Kなら成績x以下にすることができる

# 各整数について命題はFalseかTrueを返す
# その順番は1から順にF...FT...Tとなる
# この一番左のTの整数xが求めたい最小値：チームの成績xの最小値

a.sort()
f.sort(reverse=True)

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        syugyo += max(A-int(x/F),0)
    if syugyo <= k:
        return True
    else:
        return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)
    
# 計算量は 1+2logN + N*log(2)N <= N*logN < 3.6 * 10^6 
# ぎりぎりセーフ？
### BUGGY CODE ###

n = int(input())

power = 1
for i in range(1, n+1):
  power *= i
print(power % (10**9+7))

### FIXED CODE ###

import math
print(math.factorial(int(input()))%(10**9+7))
### BUGGY CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
n = int(input())
v = list(map(int, input().split()))
ev = []
od = []
for i in range(n):
    if i % 2 == 0:
        ev.append(v[i])
    else:
        od.append(v[i])
ev.sort()
od.sort()
m = 0
oo = [[0, 0]]
ii = [[0, 0]]
while True:
    oo.append([ev[m], br(ev, ev[m], 0, n//2)-bl(ev, ev[m], 0, n//2)])
    m += ev.count(ev[m])
    if m >= n//2:
        break
m = 0
while True:
    ii.append([od[m], br(od, od[m], 0, n//2)-bl(od, od[m], 0, n//2)])
    m += od.count(od[m])
    if m >= n//2:
        break
ii.sort(key=lambda x: x[1], reverse=True)
oo.sort(key=lambda x: x[1], reverse=True)
if ii[0][0] != oo[0][0]:
    print(n - oo[0][1] - ii[0][1])
else:
    print(min(n - oo[1][1] - ii[0][1], n - oo[0][1] - ii[1][1]))

### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
ev = [0]*(max(v)+1)
od = [0]*(max(v)+1)
for i in range(n):
    if i % 2 == 0:
        ev[v[i]-1] += 1
    else:
        od[v[i] - 1] += 1
e = sorted(ev)
o = sorted(od)
if ev.index(e[-1]) == od.index(o[-1]) and e[-2] != e[-1] and o[-2] != o[-1]:
    print(n-max(e[-1]+o[-2], e[-2]+o[-1]))
else:
    print(n-e[-1]-o[-1])
### BUGGY CODE ###

N = int(input())
s = [input() for i in range(N)]

n = N
max_num = 0
t = []
while n >= max_num:
    word = s[0]
    count = 0
    for i in s:
        if i == word:
            count += 1

    if count > max_num:
        max_num = count
        t = [s[0]]
    elif count == max_num:
        t.append(s[0])

    s = [i for i in s if i != word]
    n = len(s)

t = sorted(t)
for i in t:
  print(i)


### FIXED CODE ###

import collections

N = int(input())
s = [input() for i in range(N)]

c = collections.Counter(s)
max_num = max(c.values())
d = []
for key,value in c.items():
  if value == max_num:
    d.append(key)

for i in sorted(d):
  print(i)
### BUGGY CODE ###

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

dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1
for i, a in  enumerate(A, 1):
  for s in range(S+1):
    dp[i][s] = 2*dp[i-1][s]
    if a <= s:
      dp[i][s] += dp[i-1][s-a]
    dp[i][s] %= MOD

print(dp[-1][-1])

### FIXED CODE ###

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

dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1
for i, a in  enumerate(A, 1):
  for s in range(S+1):
    dp[i][s] = 2*dp[i-1][s]
    if a <= s:
      dp[i][s] += dp[i-1][s-a]
    dp[i][s] %= MOD

print(dp[-1][-1])
### BUGGY CODE ###

N = int(input())
nums = list(map(int, input().split()))
count = [0]*N
nums.sort()
answer = N
for i in range(N):
  fNum = nums[i]
  for j in range(N):
    sNum = nums[j]
    if (sNum > fNum):
      break
    elif (i == j):
      continue
    else:
      if (fNum%sNum == 0):
        answer -= 1
        break

print(answer)


### FIXED CODE ###

N = int(input())
nums = list(map(int, input().split()))
nums.sort()
div_length = max(nums)+1
divisible_list = {}
#initialize
for i in range(0, div_length):
  divisible_list[i] = 0

#count divisible numbers
for fNum in nums:
  for j in range(fNum, div_length, fNum):
   	divisible_list[j] += 1

#check for numbers
answer = 0
for num in nums:
  if (divisible_list[num] == 1):
    answer += 1
print(answer)
### BUGGY CODE ###

def main():
    r, c, k = map(int, input().split())
    d = dict()
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[(t1-1, t2-1)] = t3
    dp = [[0]*4 for _ in [0]*c]
    if (0, 0) in d:
        dp[0][1] = d[(0, 0)]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        if (x, y+1) in d:
                            dp[y+1][z+1] = max(dp[y+1]
                                               [z+1], dp[y][z]+d[(x, y+1)])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                if (x+1, y) in d:
                    dp2[y][1] = max(dp2[y][1],
                                    max(dp[y])+d[(x+1, y)])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()


### FIXED CODE ###

def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()
### BUGGY CODE ###


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

#b_init = sum(A)//N - N*(N+1)//(2*N)
b_init = min(A) + N*(N+1)//(2*N)

while 1:
    #calculate sadness
    sadness = sum([abs(A[i] - (b_init+(i+1))) for i in range(N)])
    sadness_plus1 = sum([abs(A[i] - (b_init+1+(i+1))) for i in range(N)])
    sadness_minus1 = sum([abs(A[i] - (b_init-1+(i+1))) for i in range(N)])
    
    # initial equal ans
    if sadness <= sadness_plus1 and sadness <= sadness_minus1:
        print(sadness)
        break
    
    # right way
    if sadness_plus1 < sadness:
        sad_righter = sadness_plus1
        b = b_init
        while sad_righter <= sadness:
            b+=1
            sadness = sad_righter
            sad_righter = sum([abs(A[i] - (b+(i+1))) for i in range(N)])
    
        print(sadness)
        break
    
    # left way
    if sadness_minus1 < sadness:
        sad_lefter = sadness_minus1
        b = b_init
        while sad_lefter <= sadness:
            b-=1
            sadness = sad_lefter
            sad_lefter = sum([abs(A[i] - (b+(i+1))) for i in range(N)])
    
        print(sadness)
        break

### FIXED CODE ###

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

if N==1:
    print(0)
else:
    B = [A[i]-i for i in range(N)]
    B.sort()
    b_pl = B[N//2]
    b_mn = B[N//2-1]
    
    sadness_pl = sum([abs(B[i]-b_pl) for i in range(N)])
    sadness_mn = sum([abs(B[i]-b_mn) for i in range(N)])
    
    print(min(sadness_pl, sadness_mn))
### BUGGY CODE ###

a=1;c={"R":0,"G":0,"B":0}
for i in range(int(input())):
	a*=-~i
for i in input():
	s=sorted(c.values())
	c[i]+=1
	if c[i]>s[2]:
		pass
	elif c[i]>s[1]:
		a*=s[2]-s[1]
	else:
		a*=s[1]-s[0]
print(a%998244353)

### FIXED CODE ###

import math
n=int(input())
c={"R":0,"G":0,"B":0}
a=1
mod=998244353
for i in input():
	s=sorted((c["R"],c["G"],c["B"]))
	c[i]+=1
	if c[i]>s[2]:
		pass
	elif c[i]>s[1]:
		a*=s[2]-s[1]
	else:
		a*=s[1]-s[0]
	a%=mod
print(math.factorial(n)*a%mod)
### BUGGY CODE ###

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

seki = 1

for a_i in A:
        seki *= a_i

count = 0

while seki % 2 == 0:
        seki = seki // 2
        count += 1

print(count)

### FIXED CODE ###

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

for a_i in A:
        seki *= a_i

count = 0

while seki % 2 == 0:
        seki = seki // 2
        count += 1
'''

count = 0

for a_i in A:
        while a_i % 2 == 0:
                a_i = a_i // 2
                count += 1
print(count)
### BUGGY CODE ###

import sys
import heapq
import operator as op

inf = float("inf")

def dijkstra(graph, start):
    dist = [inf for _ in range(len(graph))]
    dist[start] = 0
    prev = [None for _ in range(len(graph))]
    q = [(0, start)]
    rem = len(graph) - 1

    while q != [] and rem > 0:
        du, u = heapq.heappop(q)
        if dist[u] < du:
            continue
        rem -= 1

        for v, d in graph[u].items():
            if dist[v] > du + d:
                dist[v] = du + d
                prev[v] = u
                heapq.heappush(q, (dist[v], v))

    return dist, prev

n, m, s, t = map(int, next(sys.stdin).split(" "))

yen_graph = [dict() for _ in range(n)]
snuke_graph = [dict() for _ in range(n)]

for line in sys.stdin.readlines():
    u, v, a, b = map(int, line.strip().split(" "))
    yen_graph[u-1][v-1] = yen_graph[v-1][u-1] = a
    snuke_graph[u-1][v-1] = snuke_graph[v-1][u-1] = b

yen_costs, _ = dijkstra(yen_graph, s-1)
snuke_costs, _ = dijkstra(snuke_graph, t-1)
total_costs = list(map(op.add, yen_costs, snuke_costs))

for i in range(n):
    print(10**15 - min(total_costs[i:]))


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from itertools import accumulate
 
def dijkstra(n, edges, start, *, adj_matrix=False, default_value=float("inf")):
    inf = float("inf")
    vertices = [inf] * n
    vertices[start] = 0
    q, rem = [(0, start)], n - 1
 
    while q and rem:
        cost, v = heappop(q)
        if vertices[v] < cost:
            continue
        rem -= 1
 
        dests = ((i, n) for i, n in enumerate(edges[v]) if n != default_value)\
            if adj_matrix else edges[v]
 
        for dest, _cost in dests:
            newcost = cost + _cost
            if vertices[dest] > newcost:
                vertices[dest] = newcost
                heappush(q, (newcost, dest))
 
    return vertices
 
n, m, s, t = map(int, input().split())
s, t = s-1, t-1
yen = [[] for _ in [0]*n]
sno = [[] for _ in [0]*n]
for l in sys.stdin.readlines():
    u, v, a, b = map(int, l.strip().split())
    yen[u-1].append((v-1, a))
    yen[v-1].append((u-1, a))
    sno[u-1].append((v-1, b))
    sno[v-1].append((u-1, b))
 
yen = dijkstra(n, yen, s)
sno = dijkstra(n, sno, t)
result = list(accumulate([y+s for y, s in zip(yen, sno)][::-1], min))
money = 10**15
for n in result[::-1]:
    print(money-n)
### BUGGY CODE ###

N=input()
S={"R":[],"G":[],"B":[]}
for i,s in enumerate(input()):
	S[s].append(i)

lis = [[a,b,c] for a in S["R"] for b in S["G"] for c in S["B"]]
ans = 0
for i,j,k in lis:
	if i > k:
		tmp = k
		k = i
		i = tmp
	if j > k:
		tmp = k
		k = j
		j = tmp
	if i > j:
		tmp = j
		j = i
		i = tmp	
	if j-i!=k-j:
		ans+=1
print(ans)


### FIXED CODE ###

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

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

for i in range(N):
	for j in range(N-i):
		if i+2*j>=N:
			break
		elif S[i]!=S[i+j] and S[i]!=S[i+2*j] and S[i+j]!=S[i+2*j]:
			ans-=1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


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


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


MOD = pow(10, 9)+7

N = z()
A = zz()
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ans += A[i]*A[j]
        ans %= MOD
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


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


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


MOD = pow(10, 9)+7

N = z()
A = zz()
ans = 0
part_sum = [0]*N
part_sum[0] = A[0]
sum_a = sum(A) % MOD
for i in range(1, N):
    part_sum[i] = (part_sum[i-1] + A[i]) % MOD

for i in range(N - 1):
    tmp = A[i]*(sum_a - part_sum[i])
    ans = (ans+tmp) % MOD
    ans = ans % MOD
print(ans)

# for i in range(N):
#     for j in range(i + 1, N):
#         ans += A[i]*A[j]
#         ans %= MOD
# print(ans)
### BUGGY CODE ###

from collections import *
from itertools import *

N = int(input())

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

ABI = sorted(((a, max(N-i, i-1)*a, i) for i, a in enumerate(A, 1)), reverse=True)
SA, SB = map(sum, islice(zip(*ABI), 0, 2))

prev = {(0,0):0}
prev_max = 0
for a, b, i in ABI:
  curr = defaultdict(int)
  curr_max = 0
  for (l,r), p in prev.items():
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l,r+1] = max(curr[l,r+1], p+abs(N-i-r)*a)
    curr[l+1,r] = max(curr[l+1,r], p+abs(i-l-1)*a)
    curr_max = max(curr_max, curr[l,r+1], curr[l+1,r])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)


### FIXED CODE ###

from collections import *
from itertools import *

N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  curr_max = 0
  for l, p in prev.items():
    r = k-l
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
    curr_max = max(curr_max, curr[l], curr[l+1])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)