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

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

axor=[0]*n
bxor=[0]*n

for i in range(n-1):
    axor[i] = a[i] ^ a[i+1]
    bxor[i] = b[i] ^ b[i+1]

axor[-1] = a[0] ^ a[-1]
bxor[-1] = b[0] ^ b[-1]

def MP(it):
    n = len(it)
    res = [0]*(n+1)
    res[0] = -1
    j = -1
    for i in range(n):
        while j >= 0 and it[i] != it[j]:
            j = res[j]
        j += 1
        res[i+1] = j
    return res

mp = MP(bxor)
for i in range(1,len(mp)):
    mp[i] = i - mp[i]
txt = axor + axor
head = 0
ans = list()
start = 0
while head < n:
    for i in range(start,n):
        if bxor[i] != txt[head+i]:
            start = mp[i+1]-(i+1)
            head += mp[i+1]
            break
    else:
        x = b[0] ^ a[head]
        ans.append([head, x])
        start = i-mp[i+1]
        head += mp[i+1]


for k,x in ans:
    print(k,x)

### FIXED CODE ###

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

axor=[0]*n
bxor=[0]*n

for i in range(n-1):
    axor[i] = a[i] ^ a[i+1]
    bxor[i] = b[i] ^ b[i+1]

axor[-1] = a[0] ^ a[-1]
bxor[-1] = b[0] ^ b[-1]

def MP(it):
    n = len(it)
    res = [0]*(n+1)
    res[0] = -1
    j = -1
    for i in range(n):
        while j >= 0 and it[i] != it[j]:
            j = res[j]
        j += 1
        res[i+1] = j
    return res

mp = MP(bxor)
shift = [1]*(n+1)
for i in range(n):
    shift[i+1] = i+1 - mp[i+1]
txt = axor + axor
head = 0
ans = list()
start = 0
while head < n:
    for i in range(start,n):
        if bxor[i] != txt[head+i]:     
            start = max(0,i - shift[i])
            head += shift[i]
            break
    else:
        x = b[0] ^ a[head]
        ans.append([head, x])
        start = i+1 - shift[i+1]
        head += shift[i+1]


for k,x in ans:
    print(k,x)
### BUGGY CODE ###

N = int(input())
n = len(str(N)) - 1
ans = 0
for i in range(3, n+1):
  ans += 3**i - (2**i)*3 + 3

t = 3**n - 2**(n+1) + 1

if int(str(N)[0]) == 3:
  for i in range(3*(10**n), N+1):
    s = set([j for j in str(i)])
    if ('5' in s) and ('7' in s) and (len(s)==3):
      ans += 1
elif int(str(N)[0]) == 4:
  ans += t
elif int(str(N)[0]) == 5:
  ans += 3**n - (2**n)*3 + 3 + 2**n - 2
  for i in range(5*(10**n), N+1):
    s = set([j for j in str(i)])
    if ('3' in s) and ('7' in s) and (len(s)==3):
      ans += 1
elif int(str(N)[0]) == 6:
  ans += 2*t
elif int(str(N)[0]) == 7:
  ans += 2*t
  for i in range(7*(10**n), min(N+1, 8*(10**n))):
    s = set([j for j in str(i)])
    if ('3' in s) and ('5' in s) and (len(s)==3):
      ans += 1
elif int(str(N)[0]) > 7:
  ans += 3*t
print(ans)


### FIXED CODE ###

N = int(input())

def dfs(n):
  if int(n) > N:
    return 0
  if ('3' in n) and ('5' in n) and ('7' in n):
    ret = 1
  else:
    ret = 0
  for c in '357':
    ret += dfs(n+c)
  return ret

print(dfs('0'))
### BUGGY CODE ###

import numpy as np
import heapq

INF=10**15
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append([R,C])
    adj[R].append([L,C])
for i in range(N-1):
    adj[i+1].append([i,0])
    
s=0
g=N-1
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,[s,table[s]])
                
while heap:
    q=heapq.heappop(heap)
    a=q[0]
    if q[1]>table[a]: continue
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if table[p]>table[a]+co:
            table[p]=table[a]+co
            heapq.heappush(heap,[p,table[p]])
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import numpy as np
import heapq

INF=10**15
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(table[s],s))
                
while heap:
    q=heapq.heappop(heap)
    a=q[1]
    if q[0]>table[a]: continue
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if table[p]>table[a]+co:
            table[p]=table[a]+co
            heapq.heappush(heap,(table[p],p))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

#
import sys

def input(): return sys.stdin.readline().strip()

def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

    for i in range(n):
        al = list(map(int, input().split()))
        for j in range(len(al)):
            al[j] -= 1
        agrid.append(al)

    ans = 0

    while True:
        match = set()
        for i in range(n):
            if agrid_pointer[i] == n - 1 or i in match:  # もう全部対戦済み or この日対戦済み
                continue

            target = agrid[i][agrid_pointer[i]]
            if agrid_pointer[target] == n - 1 or target in match:  # もう全部対戦済み or この日対戦済み
                continue
            # i, target は対戦可能

            if agrid[target][agrid_pointer[target]] != i:
                continue

            # can match
            agrid_pointer[i] += 1
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)

            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#
import sys
import time

def input(): return sys.stdin.readline().strip()

def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

    start = time.time()

    for i in range(n):
        al = list(map(int, input().split()))
        agrid.append(al)

    ans = 0

    while True:
        match = set()
        for i in range(n):
            if agrid_pointer[i] == n - 1 or i in match:  # もう全部対戦済み or この日対戦済み
                continue

            target = agrid[i][agrid_pointer[i]] - 1
            if agrid_pointer[target] == n - 1 or target in match:  # もう全部対戦済み or この日対戦済み
                continue
            # i, target は対戦可能

            if agrid[target][agrid_pointer[target]] - 1 != i:
                continue

            # can match
            agrid_pointer[i] += 1
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)

            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        elapsed_time = time.time() - start
        if elapsed_time > 1.5:
            print(n * (n-1)//2)
            return

        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


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

def main():
    k = int(input())
    alt_7 = 7
    mod_k = 7
    count = 1
    while alt_7 % k != 0:
        mod_k = mod_k * 10 % k
        if mod_k == 0:
            print(-1)
            return
        alt_7 += mod_k
        count += 1
    print(count)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    k = int(input())
    a = [1]
    a.append(7 % k)
    [a.append((a[i-1] * 10 + 7) % k) for i in range(2, k+1)]
    for i in range(1, k+1):
        if a[i] == 0:
            print(i)
            return
    print(-1)

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

# -*- coding: utf-8 -*-

import sys
import math


debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        for line in sys.stdin:
            lines.append(line.strip())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    (n, ) = [int(e) for e in lines[0].split(' ')]

    return (n, )


def solve(n, ):

    
    a = []
    tmp = n
    total = 0
    while tmp > 0:
        #q = tmp // 10
        #r = tmp % 10
        (q, r) = divmod(tmp, 10)
        #a.append(r)
        total = total + r
            
        tmp = q

    a.reverse()
    if debug:
        log("a=%s" % a)

    result = 'No' 
    #if sum(a) % 9 == 0:
    if total % 9 == 0:
        result = 'Yes'


    return result 


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import math


debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        for line in sys.stdin:
            lines.append(line.strip())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    n = lines[0]

    return (n, )


def solve(n, ):

    
    total = sum([int(e) for e in n])

    result = 'No' 
    #if sum(a) % 9 == 0:
    if total % 9 == 0:
        result = 'Yes'


    return result 


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()
### BUGGY CODE ###

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

ans = 0
for i in range(K, N+1, K):
    for j in range(K, N+1, K):
        for k in range(K, N+1, K):
            ans += 1
if K % 2 == 0:
    for i in range(K//2, N+1, K):
        for j in range(K//2, N+1, K):
            for k in range(K//2, N+1, K):
                ans += 1
print(ans)

### FIXED CODE ###

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

ans = 0
cnt = 0
for i in range(K, N+1, K):
    cnt += 1
ans += pow(cnt, 3)

if K % 2 == 0:
    cnt = 0
    for i in range(K//2, N+1, K):
        cnt += 1
    ans += pow(cnt, 3)
print(ans)
### BUGGY CODE ###

import numpy as np
N,K,Q = map(int,input().split())
point = np.array([K for i in range(0,N)])
minus = np.array([-1 for i in range(0,N)])
for i in range(0,Q):
    A = int(input())
    point += minus
    point[A-1] += 1
for i in range(0,N):
    if point[i] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K,Q = map(int,input().split())
point = [0 for i in range(0,N)]
for i in range(0,Q):
    A = int(input())
    point[A-1] += 1
for i in range(0,N):
    if Q - point[i] < K:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

sa = sum(A)
m = 1
divs = set()
while m*m <= sa:
    if sa%m == 0:
        divs.add(m)
        divs.add(sa//m)
    m += 1

for d in sorted(divs,reverse=True):
    mods = []
    for a in A:
        mods.append(a%d)
    mods.sort()
    if all(m==0 for m in mods):
        print(d)
        exit()
    for i in range(N-1):
        plus = minus = 0
        for j,m in enumerate(mods):
            if j <= i:
                plus += m
            else:
                minus += d-m
        if plus == minus and plus <= K:
            print(d)
            exit()

### FIXED CODE ###

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

sa = sum(A)
m = 1
divs = set()
while m*m <= sa:
    if sa%m == 0:
        divs.add(m)
        divs.add(sa//m)
    m += 1

for d in sorted(divs,reverse=True):
    mods = []
    for a in A:
        mods.append(a%d)
    mods.sort()
    if all(m==0 for m in mods):
        print(d)
        exit()

    cump = [0]
    for m in mods:
        cump.append(cump[-1] + m)
    cumm = [0]
    for m in reversed(mods):
        cumm.append(cumm[-1] + (d-m))
    for i in range(1,N):
        if cump[i] == cumm[N-i] and cump[i] <= K:
            print(d)
            exit()
### BUGGY CODE ###

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

import itertools
import copy

counter = 0
flag_list = [i for i in range(2*N)]
flag = itertools.combinations(flag_list, N)


for f in flag:
    red = ""
    s = copy.copy(S)
    for i in f:
        red += s[i]
        s[i] = "0"
    blue = "".join(s)[::-1].replace("0", "")
    if red == blue:
        counter += 1


print(counter)

### FIXED CODE ###

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

S1, S2 = S[:N], S[N:][::-1]

dic = {}
keys = []
Ans = 0

for i in range(2 ** N):
    red, blue, red2, blue2 = "", "", "", ""
    # 半分ずつbit全探索
    bits = bin(2 ** N + i)[3:]
    for j in range(N):
        if bits[j] == "0":
            red += S1[j]
            red2 += S2[j]
        else:
            blue += S1[j]
            blue2 += S2[j]
    # あとで数える際に使うので記録しておく
    keys.append(red2 + "-" + blue2)
    # 半分全列挙
    key = red + "-" + blue
    if key not in dic.keys():
        dic[key] = 1
    else:
        dic[key] += 1

for key in keys:
    Ans += dic.get(key, 0)

print(Ans)
### BUGGY CODE ###

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

sum = 0

for i in range(n):
    xor = a[i]
    count = bin(a[i]).count('1')
    for j in range(i+1, n):
        xor = xor ^ a[j]
        count = count + bin(a[j]).count('1')
        if bin(xor).count('1') == count:
            sum += 1
        else:
            break

print(sum+n)


### FIXED CODE ###

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

res = 0
sum = 0
r = 0

for l in range(n):
    while r < n and (sum + a[r]) == (sum ^ a[r]):
        sum += a[r]
        r += 1
    res += r - l
    if l == r:
        r += 1
    else:
        sum -= a[l]

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

s=input()
b=len(s)
while "01" in s or "10" in s:
        s=s.replace("01","")
        s=s.replace("10","")
print(b-len(s))

### FIXED CODE ###

s=input()
c0=s.count("0")
c1=s.count("1")
print(len(s)-abs(c0-c1))
### BUGGY CODE ###

N=int(input())
S=list(map(int,input().split()))
lenS=len(S)
T=[]
for i in range(1,N+1):
    T.append(abs(i-(N+1-i)))

T.sort()
S.sort()

def mal(a):
    return (a*2)%(10**9+7)

for i in range(N):
    if T!=S:
        print(0)
        exit()


ans=1
for i in range(lenS//2):
    
    ans=mal(ans)

print(ans)


    

### FIXED CODE ###

N=int(input())
S=list(map(int,input().split()))
lenS=len(S)
T=[]
for i in range(1,N+1):
    T.append(abs(i-(N+1-i)))

T.sort()
S.sort()



for i in range(N):
    if T[i]!=S[i]:
        print(0)
        exit()


ans=1
nagasa=lenS//2
for i in range(nagasa):
    
    ans=(ans*2)%(10**9+7)

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

S = input()
Q = int(input())
reverse = False
for _ in range(Q):
    tmp = input().split()
    q = int(tmp[0])
    if q == 1:
        reverse = not reverse
    elif q == 2:
        f = int(tmp[1])
        if f == 1:
            if reverse:
                S = S + tmp[2]
            else:
                S = tmp[2] + S
        elif f == 2:
            if reverse:
                S = tmp[2] + S
            else:
                S = S + tmp[2]
if reverse:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
d = deque()
d.append(S)
reverse = False
for _ in range(Q):
    tmp = input().split()
    q = int(tmp[0])
    if q == 1:
        reverse = not reverse
    elif q == 2:
        f = int(tmp[1])
        if f == 1:
            if reverse:
                d.append(tmp[2])
            else:
                d.appendleft(tmp[2])
        elif f == 2:
            if reverse:
                d.appendleft(tmp[2])
            else:
                d.append(tmp[2])
S = "".join(d)
if reverse:
    print(S[::-1])
else:
    print(S)
### BUGGY CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[0 for i in range(n)]
c=1
k=min(k,40)

while c<=k:
    b=[0 for i in range(n)]
    for i in range(n):
        l=max(0,i-a[i])
        r=min(n-1,i+a[i])
        b[l]+=1
        if r+1<n:
            b[r+1]-=1
    for i in range(1,n):
        b[i]+=b[i-1]
    c+=1
    a=b

print(" ".join(map(str,a)))

### FIXED CODE ###

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

for j in range(k):
    b=[0 for i in range(n)]
    for i in range(n):
        l=max(0,i-a[i])
        r=min(n-1,i+a[i])
        b[l]+=1
        if r+1<n:
            b[r+1]-=1
    for i in range(1,n):
      b[i]+=b[i-1]
    a=b
print(" ".join(map(str,a)))
### BUGGY CODE ###

N=int(input())
S=[]
Word=set()
for i in range(N):
    s=input()
    Word.add(s)
    S.append(s)
Word=list(Word)
ans=[[0]*2 for i in range(len(Word))]
maxcnt=0
for k in range(len(Word)):
    ans[k][0]=Word[k]
    ans[k][1]=S.count(Word[k])
    maxcnt=max(maxcnt,ans[k][1])
ans=sorted(ans)
for i in range(len(Word)):
    if ans[i][1]==maxcnt:
        print(ans[i][0])

### FIXED CODE ###

from collections import*
n,*s=open(0)
cnt=Counter(s).most_common()
ans=sorted(a*(b==cnt[0][1])for a,b in cnt)
for i in ans:
    print(i,end="")
### BUGGY CODE ###

import sys
import os

MOD = 2019


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    L, R = list(map(int, sys.stdin.readline().split()))
    ret = float('inf')

    for i in range(L, R+1):
        for j in range(i+1, R+1):
            ret = min(ret, (i * j) % MOD)

    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os

MOD = 2019


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    L, R = list(map(int, sys.stdin.readline().split()))
    ret = float('inf')

    if R - L >= 2019:
        print(0)
        exit()

    for i in range(L, R+1):
        for j in range(i+1, R+1):
            ret = min(ret, (i * j) % MOD)

    print(ret)


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

import queue
import sys
input = sys.stdin.readline

N,Q=map(int,input().split())
c=[0]*N#count

to=[[] for i in range(N)]

for i in range(N-1):
    a,b =map(int,input().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
    
    
for i in range(Q):
    p,x =map(int,input().split())
    p-=1
    c[p]+=x
    
q=queue.Queue()
q.put((0,-1))


while not q.empty():
    v,prev=q.get()
    for i in range(len(to[v])):
        v_next=to[v][i]
        if v_next!=prev:
            q.put((v_next,v))
            c[v_next]+=c[v]

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

### FIXED CODE ###

import queue
import sys
input = sys.stdin.readline

N,Q=map(int,input().split())
c=[0]*N#count

to=[[] for i in range(N)]

for i in range(N-1):
    a,b =map(int,input().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
    
    
for i in range(Q):
    p,x =map(int,input().split())
    p-=1
    c[p]+=x
    
q=queue.Queue()
q.put((0,-1))


while not q.empty():
    v,prev=q.get()
    for i in range(len(to[v])):
        v_next=to[v][i]
        if v_next!=prev:
            q.put((v_next,v))
            c[v_next]+=c[v]

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

a, b, x = map(int, input().split())

counter = 0
for i in range(a, b+1):
    if i % x == 0:
        counter += 1
print(counter)


### FIXED CODE ###

a, b, x = map(int, input().split())

def f(n):
    if n == -1:
        return 0
    return n // x + 1

print(f(b)-f(a-1))
### BUGGY CODE ###

import itertools
N,M = (int(i) for i in input().split())
A = sorted([int(i) for i in input().split()])
accum = list(itertools.accumulate(A))
e = []
for k, v in sorted([[int(i) for i in input().split()] for i in range(M)], key=lambda x: -x[1]):
    for _ in range(k):
        e.append(v)
for i in range(min(len(e),len(A))):
    if A[i]<e[i]:
        A[i]=e[i]
    else:
        break
print(sum(A))


### FIXED CODE ###

N,M = (int(i) for i in input().split())
A = sorted([int(i) for i in input().split()])
e,p = [(0,0)],0
for k, v in sorted([[int(i) for i in input().split()] for i in range(M)], key=lambda x: -x[1]):
    e.append((e[p][0]+k,v))
    p+=1

p = 1
for i in range(min(e[-1][0],len(A))):
    B,C = e[p]
    if A[i]<C:
        A[i]=C
    else:
        break
    if i == B-1:
        p+=1
print(sum(A))
### BUGGY CODE ###

N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
s_cost = a
cost = sum(s_cost)
for k in range(0,N):
    s_cost = [min(s_cost[x],a[y]) for (x,y) in zip( list(range(N)), list(range(N-k,N))+list(range(N-k)) )]
    if cost >= k*x + sum(s_cost):
        cost = k*x + sum(s_cost)
        # cost = min(cost, k*x + sum(s_cost))
    else:
        break
print(cost)

### FIXED CODE ###

N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
s_cost = a.copy()
cost = sum(s_cost)
for k in range(1,N):
    for i in range(N):
        if s_cost[i] > a[(i-k)%N] :
            s_cost[i] = a[(i-k)%N]
    if cost > k*x + sum(s_cost):
        cost = k*x + sum(s_cost)
    else:
        break

print(cost)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H,W,M=map(int,input().split())#slow,行数H、列数W、爆弾数M
hcnt=[0]*H#何行目に何個あるか
wcnt=[0]*W#何列目に何個あるか
bomb=[]

for i in range(M):
    bh,bw=map(int,input().split())
    hcnt[bh-1]+=1#行方向
    wcnt[bw-1]+=1#列方向
    bomb.append([bh-1,bw-1])
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[1,1],[0,0],[0,2]]
hmax=max(hcnt)#2
wmax=max(wcnt)#1
hmaxindex=[i for i in range(H) if hcnt[i]==hmax]#[0]
wmaxindex=[i for i in range(W) if wcnt[i]==wmax]#[0,1,2]
#crosspoint has not bomb

for i in hmaxindex:
    for j in wmaxindex:
        if [i,j] not in bomb:
            print(hmax+wmax)
            sys.exit()
        else:
            continue
#all crosspoint has bomb
print(hmax+wmax-1)

### FIXED CODE ###


import sys
from collections import Counter

H, W, M = map(int, sys.stdin.readline().rstrip().split())#行数H、列数W、爆弾数M
hcnt = [0] * H#何行目に何個あるか
wcnt = [0] * W#何列目に何個あるか
bomb = []

for i in range(M):
    bh,bw=map(int,sys.stdin.readline().rstrip().split())
    hcnt[bh - 1] += 1#行方向
    wcnt[bw - 1] += 1#列方向
    bomb.append((bh - 1,bw - 1))
#hcnt [2,1]
#wcnt[1,1,1]
#bomb[[1,1],[0,0],[0,2]]
hmax = max(hcnt)#2
wmax = max(wcnt)#1

crs = 0#hmax and wmax crosspoint
for (i, j) in bomb:
    if hcnt[i] == hmax and wcnt[j] == wmax:
        crs += 1
#all crosspoint has bomb
if crs == Counter(hcnt)[hmax] * Counter(wcnt)[wmax]:
    print(hmax + wmax - 1)
#more than one crosspoint has no bomb
else:
    print(hmax + wmax)
### BUGGY CODE ###

N = int(input())
print(sum([ i for i in range(1, N)]))

### FIXED CODE ###

N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

N = int(input())
l = []
for i in map(int, input().split()):
    if i in l:
        print("NO")
        exit(0)
    l.append(i)
print("YES")

### FIXED CODE ###

N = int(input())
A = set(map(int, input().split()))
print("YES" if len(A) == N else "NO")
### BUGGY CODE ###

from scipy.special import comb
from collections import Counter, deque

D = deque(map(int, list(input())))
num_mod = {}
value = 0

for i in range(len(D)):
    value = value + D.pop() * 10**i
    modulo = value % 2019
    #print(modulo)
    if modulo in num_mod.keys():
        num_mod[modulo] += 1
    else:
        num_mod[modulo] = 1

fix = 0
ans = [comb(i, 2, exact=True) for i in num_mod.values() if i > 1]
#print(b)
if 0 in num_mod.keys():
    if num_mod[0] == 1:
        fix = 1
print(sum(ans)+fix)


### FIXED CODE ###

import sys
from collections import deque
def input():
    return sys.stdin.readline()[:-1]

S = deque(map(int, list(input())))
num = 0
dict = {}
dict[0] = 1
ans = 0

for i in range(len(S)):
    num += S.pop() * pow(10,i,2019)
    cand = num % 2019
    if cand in dict.keys():
        dict[cand] += 1
    else:
        dict[cand] = 1

for key in dict.keys():
    ans += dict[key] * (dict[key] - 1) // 2
print(ans)
### BUGGY CODE ###

n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(0,n-1):
    for j in range(i+2,n+1):
        ans+=sorted(set(p[i:j]))[-2]
print(ans)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)