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

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

R, G, B = [], [], []
for i, c in enumerate(s):
  if c == 'R': R.append(i)
  elif c == 'G': G.append(i)
  else: B.append(i)

d = dict({'R':len(R), 'G':len(G), 'B':len(B)})
ds = sorted(d.items(), key=lambda x: x[1])

if ds[0][0] == 'R': X1 = R
elif ds[0][0] == 'G': X1 = G
else: X1 = B
if ds[1][0] == 'R': X2 = R
elif ds[1][0] == 'G': X2 = G
else: X2 = B
if ds[2][0] == 'R': X3 = R
elif ds[2][0] == 'G': X3 = G
else: X3 = B

ans = 0
for a in X1:
  for b in X2:
    if a < b: x, y = a, b
    else: x, y = b, a

    ans += len(X3)
    if x*2 - y >= 0:
      if x*2 - y in X3: ans -= 1
    if (x + y) % 2 == 0:
      if (x+y)//2 in X3: ans -= 1
    if y*2 - x in X3: ans -= 1

print(ans)

### FIXED CODE ###

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

R, G, B = [], [], []
for i, c in enumerate(s):
  if c == 'R': R.append(i)
  elif c == 'G': G.append(i)
  else: B.append(i)

ans = 0
for r in R:
  for g in G:
    if r < g: x, y = r, g
    else: x, y = g, r

    ans += len(B)
    if x*2 - y >= 0:
      if s[x*2 - y] == 'B': ans -= 1
    if (x + y) % 2 == 0:
      if s[(x+y)//2] == 'B': ans -= 1
    if y*2 - x < len(s):
      if s[y*2 - x] == 'B': ans -= 1

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

import numpy as np
n,mondaisuu=map(int,input().split())
s=input()
li=np.zeros(n)
dp = [[0 for i in range(n)] for j in range(n)]
for i in range(n-1):
  if s[i]=="A" and s[i+1]=="C":
    li[i]=1
for i in range(mondaisuu):
  l,r=map(int,input().split())
  if dp[l-1][r-1]==0:
    ans=int(np.sum(li[l-1:r-1]))
    print(ans)
    dp[l-1][r-1]=ans
  else:
    print(dp[l-1][r-1])

### FIXED CODE ###

n,mondaisuu=map(int,input().split())
s=input()
dp=[0]*n
for i in range(1,n):
  dp[i]=dp[i-1] + (1 if s[i]=="C" and s[i-1]=="A" else 0)
for i in range(mondaisuu):
  l,r=map(int,input().split())
  print(dp[r-1]-dp[l-1])
### BUGGY CODE ###

n = int(input())
s = [int(i) for i in input()]
cnt = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            tmp = 0
            for l in s:
                if i == l and tmp == 0:
                    tmp += 1
                elif j == l and tmp == 1:
                    tmp += 1
                elif k == l and tmp == 2:
                    cnt += 1
                    break
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(1000):
    i = str(i).zfill(3)
    j = s.find(i[0])
    if j != -1:
        k = s[j + 1:].find(i[1])
        if k != -1:
            if s[j + k + 2:].find(i[2]) != -1:
                cnt += 1
print(cnt)
### BUGGY CODE ###

def main():
    s = input()
    k = int(input())
    
    l = []
    for i in range(0, len(s)):
        for j in range(0, len(s)-i):
            sub = s[i:i+j+1]

            if sub not in l:
                l.append(sub)

    l.sort()
    
    print(l[k-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    k = int(input())
    
    l = []
    for i in range(0, len(s)):
        for j in range(0, min(len(s)-i, k)):
            sub = s[i:i+j+1]

            if sub not in l:
                l.append(sub)

    l.sort()
    
    print(l[k-1])

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

n, k, c = map(int, input().split())
s = list(input())
# print(s)

dp = [0] * (n + 1)
for i in reversed(range(n)):
    j = min(i + c + 1, n)
    if s[i] == 'o':
        dp[i] = max(dp[j] + 1, dp[i + 1])
    else:
        dp[i] = max(dp[j], dp[i + 1])

# print(dp)


def check(idx):
    if s[idx] == 'x':
        return False

    s[idx] = 'x'
    dp_ = [0] * (idx + 2)
    dp_[idx + 1] = dp[idx + 1]
    for i in reversed(range(idx + 1)):
        j = min(i + c + 1, idx + 1)
        if s[i] == 'o':
            dp[i] = max(dp[j] + 1, dp[i + 1])
        else:
            dp[i] = max(dp[j], dp[i + 1])
        if dp[i] >= k:
            s[idx] = 'o'
            return False

    s[idx] = 'o'
    return True


for i in range(n):
    if check(i):
        print(i + 1)


### FIXED CODE ###

n, k, c = map(int, input().split())
s = list(input())
# print(s)

dp1 = [0] * (n + 1)
for i in reversed(range(n)):
    j = min(i + c + 1, n)
    if s[i] == 'o':
        dp1[i] = max(dp1[j] + 1, dp1[i + 1])
    else:
        dp1[i] = max(dp1[j], dp1[i + 1])

dp2 = [0] * (n + 1)
for i in range(n):
    j = max(i - c - 1, -1)
    if s[i] == 'o':
        dp2[i] = max(dp2[j] + 1, dp2[i - 1])
    else:
        dp2[i] = max(dp2[j], dp2[i - 1])

# print(dp1)
# print(dp2)


def check(idx):
    if s[idx] == 'x':
        return False

    if dp1[idx + 1] + dp2[idx - 1] >= k:
        return False
    else:
        return True


for i in range(n):
    if check(i):
        print(i + 1)
### BUGGY CODE ###

import functools


@functools.lru_cache(maxsize=None)
def rec(state, v):
    if state == (1 << V) - 1 and v == 0:
        return 0
    ret = INF
    for c, w in edge[v]:
        if not (state >> c & 1):
            ret = min(ret, rec(state | 1 << c, c) + w)
    return ret

INF = 10**6
V, E = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
    s, t, w = map(int, input().split())
    edge[s].append((t, w))
ans = rec(0, 0)
print(ans if ans != INF else -1)

### FIXED CODE ###

def read_list(t): return [t(x) for x in input().split()]
def read_line(t): return t(input())
def read_lines(t, N): return [t(input()) for _ in range(N)]

INF = 1<<27
V, E = read_list(int)
edge = [[] for _ in range(V)]
for _ in range(E):
    fr, to, cost = map(int, input().split())
    edge[fr].append((to, cost))

dp = [[INF] * V for _ in range(1<<V)]
dp[(1 << V) - 1][0] = 0
for state in reversed(range((1<<V)-1)):
    for v in range(V):
        for to, cost in edge[v]:
            if not (state >> to & 1):
                dp[state][v] = min(dp[state][v], dp[state | 1 << to][to] + cost)
print(dp[0][0] if dp[0][0] != INF else -1)
### BUGGY CODE ###

from collections import deque
N = int(input())
a = deque()
a_num = 0
b =deque()
c = deque()
for i in range(N):
  a_num = int(input())
  a.append(a_num)
  k,p=0,0
  x = [0]*N
  b_num=deque()
  for i in range(a_num):
    k,p = map(int,input().split())
    b_num.append(k-1)
    x[k-1]=p
  b.append(b_num)
  c.append(x)
max_num = 0   
for i in range(2**N):
  two = format(i,"015b")
  two = two[::-1]
  flag=True
  for i,k in enumerate(two):
    if i<N:
      if k =="1":
        for l in range(a[i]):
          for j in b[i]:
            #print(b[i],c[i][j],two[j])
            if c[i][j]!=int(two[j]):
              flag =False
              break
  if flag == True:
    #print(two)
    max_num = max(max_num,two.count("1"))  
print(max_num)

### FIXED CODE ###

from collections import deque
N = int(input())
a = deque()
a_num = 0
b =deque()
c = deque()
for i in range(N):
  a_num = int(input())
  a.append(a_num)
  k,p=0,0
  x = [0]*N
  b_num=deque()
  for i in range(a_num):
    k,p = map(int,input().split())
    b_num.append(k-1)
    x[k-1]=p
  b.append(b_num)
  c.append(x)
max_num = 0   
for i in range(2**N):
  two = format(i,"015b")
  two = two[::-1]
  flag=True
  for i,k in enumerate(two):
    if flag == False:
      break
    if i<N:
      if k =="1":
        for l in range(a[i]):
          for j in b[i]:
            #print(b[i],c[i][j],two[j])
            if c[i][j]!=int(two[j]):
              flag =False
              break
          if flag ==False:
            break
        if flag == False:
          break
    
    else:
      break
  if flag == True:
    #print(two)
    max_num = max(max_num,two.count("1"))  
print(max_num)
### BUGGY CODE ###

n = int(input())
s = input()
sumnum = 0

if (n == 1) or (n == 2):
    print(0)
    exit()

for k in range(3, n + 1):
    for j in range(2, k):
        for i in range(1, j):
            if (s[i - 1] != s[j - 1]) and (s[j - 1] != s[k - 1]) and (s[k - 1] != s[i - 1]):
                if j - i != k - j:
                    sumnum += 1

print(sumnum)



### FIXED CODE ###

n = int(input())
s = input()
firstcond = s.count('R') * s.count('G') * s.count('B')
minus = 0

for k in range(3, n + 1):
    for j in range(2, k):
        i = 2 * j - k
        if 1 <= i < j:
            if (s[i - 1] != s[j - 1]) and (s[j - 1] != s[k - 1]) and (s[k - 1] != s[i - 1]):
                minus += 1

print(firstcond - minus)
### BUGGY CODE ###

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

arr = []
for x in range(10**5):
    count = 0
    for i in range(n):
        if a[i] == x-1 or a[i] == x or a[i] == x+1:
            count += 1
    arr.append(count)

print(max(arr))


### FIXED CODE ###

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

arr = [0] * (10**5 + 2)
for i in range(n):
    arr[a[i]] += 1
ans = []
for x in range(1,10**5):
    ans.append(arr[x-1] + arr[x] + arr[x+1])

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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
from collections import Counter

n,x,y=map(int,input().split())

fr,to,w=[],[],[]

for i in range(n-1):
  fr.append(i)
  to.append(i+1)
  w.append(1)

fr.append(x-1)
to.append(y-1)
w.append(1)

g=csr_matrix((w, (fr, to)), shape=(n, n))

ans_l=[]
for i in range(n):
  d=dijkstra(g,indices=i,directed=False)
  ans_l+=list(d)

c=Counter(ans_l)
cn=0
for i in sorted(c.keys()):
  if cn>=1:
    print(c[i]//2)
  cn+=1
for i in range(n-1-len(c.keys())+1):
  print(0)

### FIXED CODE ###

from collections import Counter

n,x,y=map(int,input().split())

x-=1
y-=1

dist=[]
for i in range(n-1):
  for j in range(i+1,n):
    dist.append(min(j-i,abs(i-x)+1+abs(j-y)))

c=Counter(dist)
for i in range(1,n):
  print(c[i])
### BUGGY CODE ###

import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

L = [int(v) for v in input().split()]

for v in range(L[0], L[1] + 1):
    if v <= L[0] + L[2] - 1 or v >= L[1] - L[2] + 1:
        print(v)


### FIXED CODE ###

import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

L = [int(v) for v in input().split()]

if L[1] - L[0] <= L[2]:
    L[2] = L[1] - L[0]

    for v in range(L[0], L[1] + 1):
        print(v)
    exit()

s = set()
for v in range(L[0], L[0] + L[2]):
    s.add(v)
for v in range(L[1] - L[2] + 1, L[1] + 1):
    s.add(v)

for v in sorted(s):
    print(v)
### BUGGY CODE ###

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

for i in range(M):
    b, c = list(map(int, input().split()))
    A += [c]*b
A.sort(reverse=True)

print(sum(A[:N]))


### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
cards = [list(map(int, input().split())) for i in range(M)]
cards = sorted(cards, key=lambda x: x[1], reverse=True)

cnt = 0
for card in cards:
    A += [card[1]]*card[0]
    cnt += card[0]
    if cnt >= N:
        break
A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

int_n = int(input())
ar_int_a = list(map(int, input().split()))

st_int_group = set(ar_int_a)
max_count = 0

for i in st_int_group:
    # current = ar_int_a.count(i) + ar_int_a.count(i - 1) + ar_int_a.count(i + 1)
    # max_count = current if max_count <= current else max_count
    max_count = max(ar_int_a.count(i) + ar_int_a.count(i - 1) + ar_int_a.count(i + 1), max_count)

print(max_count)






### FIXED CODE ###

from collections import defaultdict

int_n = int(input())
ar_int_a = list(map(int, input().split()))

d_cnt = defaultdict(int)
for w in ar_int_a:
    d_cnt[w] += 1


st_int_group = set(ar_int_a)
max_count = 0

for i in st_int_group:
    max_count = max(d_cnt[i] + d_cnt[i - 1] + d_cnt[i + 1], max_count)

print(max_count)
### BUGGY CODE ###

from itertools import permutations


def main():
    towns, roads, visit = map(int, input().split())
    visit_order = [int(x) - 1 for x in input().split()]
    dist = [[float("inf") for _ in range(towns)] for _ in range(towns)]
    for _ in range(roads):
        a, b, d = map(int, input().split())
        a -= 1
        b -= 1
        dist[a][b] = d
        dist[b][a] = d
    for k in range(towns):
        for i in range(towns):
            for j in range(towns):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    answer = float("inf")
    for p in permutations(visit_order):
        now = 0
        for i in range(visit - 1):
            now += dist[p[i]][p[i + 1]]
        answer = min(answer, now)
    print(answer)


if __name__ == '__main__':
    main()



### FIXED CODE ###

from itertools import permutations


def main():
    towns, roads, visit = map(int, input().split())
    visit_order = [int(x) - 1 for x in input().split()]
    dist = [[float("inf") for _ in range(towns)] for _ in range(towns)]
    for _ in range(roads):
        a, b, d = map(int, input().split())
        a -= 1
        b -= 1
        dist[a][b] = d
        dist[b][a] = d
    for k in range(towns):
        for i in range(towns):
            for j in range(towns):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    answer = float("inf")
    for p in permutations(visit_order):
        now = 0
        for i in range(visit - 1):
            now += dist[p[i]][p[i + 1]]
        answer = min(answer, now)
    print(answer)


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

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################


H,W = II()
A = []
B = []
for i in range(H):
    A.append(III())
for i in range(H):
    B.append(III())


d = [[set() for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if i==0 and j==0:
            d[i][j].add(abs(A[i][j]-B[i][j]))
        elif j==0:
            for k in d[i-1][j]:
                d[i][j].add(abs(k+A[i][j]-B[i][j]))
                d[i][j].add(abs(-k+A[i][j]-B[i][j]))
        elif i==0:
            for k in d[i][j-1]:
                d[i][j].add(abs(k+A[i][j]-B[i][j]))
                d[i][j].add(abs(-k+A[i][j]-B[i][j]))
        else:
            for k in d[i-1][j]:
                if abs(k+A[i][j]-B[i][j])<=(H+W-1)*80+1:
                    d[i][j].add(abs(k+A[i][j]-B[i][j]))
                if abs(-k+A[i][j]-B[i][j])<=(H+W-1)*80+1:
                    d[i][j].add(abs(-k+A[i][j]-B[i][j]))
            for k in d[i][j-1]:
                if abs(k+A[i][j]-B[i][j])<=(H+W-1)*80+1:
                    d[i][j].add(abs(k+A[i][j]-B[i][j]))
                if abs(-k+A[i][j]-B[i][j])<=(H+W-1)*80+1:
                    d[i][j].add(abs(-k+A[i][j]-B[i][j]))

ans = 2*(H+W-1)*80+1
for i in d[H-1][W-1]:
        now = i
        if ans>now:
            ans = now
print(ans)


### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

H,W = II()
A,B,C = [],[],[]
for i in range(H):
    A.append(III())
for i in range(H):
    B.append(III())
for i in range(H):
    C.append([abs(A[i][j]-B[i][j]) for j in range(W)])

def calc(n):
    return n+80*(H+W-1)

d = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if i==0 and j==0:
            d[i][j] = 2**calc(-C[i][j]) | 2**calc(C[i][j])
        elif i==0:
            d[i][j] = (d[i][j-1]<<C[i][j]) | (d[i][j-1]>>C[i][j])
        elif j==0:
            d[i][j] = (d[i-1][j]<<C[i][j]) | (d[i-1][j]>>C[i][j])
        else:
            d[i][j] = (d[i][j-1]<<C[i][j]) | (d[i][j-1]>>C[i][j]) | \
                        (d[i-1][j]<<C[i][j]) | (d[i-1][j]>>C[i][j])

ans = (H+W-1)*80+1
for i in range(160*(H+W-1)+1):
    if (d[H-1][W-1]>>i)&1:
        val = abs(i-80*(H+W-1))
        if val<ans:
            ans = val

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

N,W = map(int,input().split())
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)
    
dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j-w[i]<0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])
    
print(dp[N][-1])

### FIXED CODE ###

import numpy as np
def main():
    N,W = map(int,input().split())
    w,v = [],[]
    for _ in range(N):
        w_,v_ = map(int,input().split())
        w.append(w_)
        v.append(v_)

    dp = np.zeros((N+1,W+1),dtype=np.int64)
    for i in range(N):
        tmp = np.zeros(W+1,dtype=int)
        tmp[w[i]:] = dp[i][:-w[i]] + v[i]
        dp[i+1] = np.maximum(dp[i],tmp)

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

N = int(input())

#data = np.array(input().split(), dtype=np.int64)


def read(): return list(map(int, input().split()))


data = read()

#count = collections.Counter(data)

for i in range(1, N+1):
    ans = data.count(i)
    print(ans)


### FIXED CODE ###

from collections import Counter

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

count = Counter(data)

for i in range(1, N+1):
    ans = count[i]
    print(ans)
### BUGGY CODE ###

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

for i in range(N):
  temp=[s[x] for x in range(i)]+[s[x] for x in range(i+1, N)]
  print(max(temp))

### FIXED CODE ###

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

temp=s.copy()
s_max=max(temp)
temp.remove(s_max)
s_max2=max(temp)

for i in range(N):
  if s[i]<s_max:
    print(s_max)
  else:
    print(s_max2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def main():
    x, k, d = map(int, input().split())

    for i in range(k):
        if x > 0:
            x -= d
            if x < 0 and (k-1-i)%2 == 0:
                print(abs(x))
                return
            elif x < 0 and (k-1-i)%2 == 1:
                print(abs(x+d))
                return
        else:
            x += d
            if x > 0 and (k-1-i)%2 == 0:
                print(abs(x))
                return
            elif x > 0 and (k-1-i)%2 == 1:
                print(abs(x-d))
                return
    print(abs(x))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def main():
    x, k, d = map(int, input().split())
    desired = abs(x) // d
    if k <= desired:
        if x < 0:
            x += k * d
        else:
            x -= k * d
        print(abs(x))
        return
    if x < 0:
        x += desired * d
    else:
        x -= desired * d
    if (k - desired) % 2 == 0:
        print(abs(x))
        return
    if x == 0:
        print(d)
    elif x > 0:
        x -= d
        print(abs(x))
    elif x < 0:
        x += d
        print(abs(x))


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


import sys
input = sys.stdin.readline
#区間の管理は　[a, b)で管理していることに注意

# INT_MIN = -10 ** 18
# MAX_N = 4 * 10 ** 5
# MAX_N = 20


def init(n_):
    #簡単にするために2のべき乗に揃える
    n = 1
    while n <= n_:
        n *= 2
    return n

#初期化
N = int(input())
n = init(N)
data = [0] * (2 * n - 1)

def update(k, a):
    k += n - 1
    data[k] = a
    while k > 0:
        data[k] = max(a, data[k])
        k = (k - 1) // 2
        # data[k] = max(data[2 * k + 1], data[2 * k + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    elif a <= l and r <= b:
        return data[k]
    else:
        v1 = query(a, b, 2 * k + 1, l, (l + r)//2)
        v2 = query(a, b, 2 * k + 2, (l + r)//2, r)
        return max(v1, v2)

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

# ans = 0
for i in range(N):
    # h = int(input())
    # a = int(input())
    h = H[i]
    a = A[i]
    tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(h, tmp + a)
    # ans = max(ans, tmp + a)
    # print (data)

print (query(1, N + 1))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

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

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

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

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

N,M = map(int,input().split())
X = list(map(int,input().split()))
Y = list(map(int,input().split()))
modulo = 10**9+7

x,y = 0,0
for i in range(N):
    for j in range(i+1,N):
        x += X[j]-X[i]
        x %= modulo
for i in range(M):
    for j in range(i+1,M):
        y += Y[j]-Y[i]
        y %= modulo

print(x*y%modulo)

### FIXED CODE ###

N,M = map(int,input().split())
X = list(map(int,input().split()))
Y = list(map(int,input().split()))
modulo = 10**9+7

x,y = 0,0
for i in range(N):
    x += X[i]*i - X[i]*(N-i-1)
for i in range(M):
    y += Y[i]*i - Y[i]*(M-i-1)

print(x*y%modulo)
### BUGGY CODE ###

N = int(input())

sum = 0
ro = 1
for n in range(1,N+1):
    num = int(N/n)
    s = int(((1+num)*num)/2)
    sum += ro*s
    ro += 1
print(sum)

### FIXED CODE ###

N = int(input())
 
sum = 0
ro = 1
for n in range(1,N+1):
    num = int(N/n)
    if num == 1:
        record = n
        break
    s = int(((1+num)*num)/2)
    sum += ro*s
    ro += 1


sum += int(((record+N)*(N-record+1))/2)
print(sum)
### BUGGY CODE ###

import math

n,m=map(int,input().split())
mod=10**9+7
a=math.factorial(n)*math.factorial(m)
if abs(n-m)==0:
    print(2*a%mod)
    exit()
if abs(n-m)>1:
    print(0)
    exit()
print(a)


### FIXED CODE ###

import math

n,m=map(int,input().split())
a=math.factorial(n) * math.factorial(m) 
if abs(n-m) == 0:
    a *= 2
elif abs(n-m) > 1:
    a = 0
print(a%1000000007)