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

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    print(0)
    g = {'Vacant':0, 'Male':1, 'Female':2}
    sl = g[input()]
    if sl == 0:
        return
    print(N-1)
    sr = g[input()]
    if sr == 0:
        return
    l = 0
    r = N-1
    while True:

        m = (l+r)//2
        print(m)
        a = g[input()]
        if a == 0:
            return
        
        if (m-l) % 2 == 1 and sl == a:
            r = m
            sr = a
        else:
            l = m
            sl = a
        




if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    g = {'Vacant':0, 'Male':1, 'Female':2}



    print(0,flush=True)
    sl = g[input()]
    if sl == 0:
        return

    print(N-1,flush=True)
    sr = g[input()]
    if sr == 0:
        return
    
    l = 0
    r = N-1
    while r-l>1:

        m = (l+r)//2
        print(m,flush=True)
        a = g[input()]
        if a == 0:
            return
        
        if (m-l) % 2 == 1:
            if sl == a:
                r = m
                sr = a
            else:
                l = m
                sl = a

        else:
            if a != sl:
                r = m
                sr = a
            else:
                l = m
                sl = a
        

    print(-1)


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

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
list = [list(map(int, input().split())) for x in range(m)]
list.sort(key=lambda x: x[1], reverse=True) # １番の要素で降順ソート


for i in list:
    a+=[i[1]]*i[0]

a.sort(reverse=True)

print(sum(a[:n]))

### FIXED CODE ###

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
list = [list(map(int, input().split())) for x in range(m)]
list.sort(key=lambda x: x[1], reverse=True) # １番の要素で降順ソート

app_count = 0
for i in list:
    a += [i[1]]*i[0]
    app_count += i[0]
    if app_count>n:
        break

a.sort(reverse=True)

print(sum(a[:n]))
### BUGGY CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(500000)
MOD = 10**9+7

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

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    N = ii()
    A = list(mi())
    d = defaultdict(int)
    ans = 1

    for a in A:
        for v in make_divisors(a):
            d[v] += 1

    for k, v in d.items():
        if v >= N-1:
            ans = max(ans, k)

    print(ans)



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from fractions import gcd
sys.setrecursionlimit(500000)
MOD = 10**9+7

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

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N = ii()
    A = list(mi())

    L = [0]*N
    R = [0]*N
    L[1] = A[0]
    R[N-2] = A[N-1]

    M = [0]*N

    for i in range(N-2):
        L[i+2] = gcd(L[i+1], A[i+1])
    for i in range(N-2, 0, -1):
        R[i-1] = gcd(R[i], A[i])

    for i in range(N):
        if L[i] == 0:
            M[i] = R[i]
        elif R[i] == 0:
            M[i] = L[i]
        else:
            M[i] = gcd(R[i], L[i])
    
    print(max(M))



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

n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  g[u].append(v)

from collections import deque
flg=False
seen=[-1]*n
mi=set(range(n))
s=0
while mi:
  s=mi.pop()
  root=[s]
  rootset={s}
  start=set(())
  todo=deque([[s,-1]])
  seen=[-1]*n
  while todo:
    v,p=todo.popleft()
    root.append(v)
    rootset.add(v)
    mi.discard(v)
    for nv in g[v]:
      if nv in rootset:
        start.add(nv)
        seen[nv]=v
        flg=True
      elif seen[nv]==-1:
        todo.append([nv,v])
        seen[nv]=v
    if flg:break
  if flg:break
if not flg:
  print(-1)
  exit()
ans=[v+1]
vv=seen[v]
ans.append(vv+1)
while vv not in start:
  vv=seen[vv]
  ans.append(vv+1)
#print(seen,s)
print(len(ans))
print(*ans,sep='\n')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  g[u].append(v)
mi=set(range(n))
flg=False
def func(path):
  chk=set(path)
  if len(path)!=2:
    for i,v in enumerate(path):
      nvs=[nv for nv in g[v] if nv in chk]
      if len(nvs)==1:continue
      for nv in nvs:
        if nv==path[(i+1)%len(path)]:continue
        ary=[nv]
        for j,vj in enumerate(path):
          if vj==nv:break
        if i>j:
          ary=path[j:i+1]
        else:
          ary=path[:i+1]+path[j:]
        #print(path,ary,i,j)
        func(ary)
  print(len(path))
  for v in path:
    print(v+1)
  exit()

def dfs(v,seen):
  mi.discard(v)
  for nv in g[v]:
    if seen[nv]!=-1:# 巡回閉路
      seen[nv]=v
      path=[v]
      chk={v}
      while seen[v] not in chk:
        v=seen[v]
        path.append(v)
        chk.add(v)
      path.reverse()
      func(path)
    else:
      seen[nv]=v
      dfs(nv,seen)
      seen[nv]=-1
while mi:
  v=mi.pop()
  seen=[-1]*n
  dfs(v,seen)
print(-1)
exit()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(200000)


def add_link(a, b):
    la = links[a]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)


def close(v, i):
    j = int(s[v] == 'B')
    for u in links[v][i].copy():
        links[u][j].discard(v)
        if not links[u][j]:
            able[u] = False
            close(u, j ^ 1)


n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    add_link(a, b)
    add_link(b, a)

for v in range(n):
    if able[v]:
        continue
    close(v, bool(links[v][1]))

print('Yes' if any(able) else 'No')


### FIXED CODE ###

import sys

sys.setrecursionlimit(200000)


def add_link(a, b):
    la = links[a]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)


def close(v, i):
    j = int(s[v] == 'B')
    for u in links[v][i].copy():
        if not able[u]:
            continue
        links[u][j].discard(v)
        if not links[u][j]:
            able[u] = False
            close(u, j ^ 1)


n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [False] * n
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    add_link(a, b)
    add_link(b, a)

for v in range(n):
    if able[v]:
        continue
    close(v, bool(links[v][1]))

print('Yes' if any(able) else 'No')
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from collections import deque
inf = 10**18
H, W, K = mapint()
y1, x1, y2, x2 = mapint()
query = [list(str(input())) for _ in range(H)]
dirc = [(0, 1), (-1, 0), (0, -1), (1, 0)]

checked = [[-1]*W for _ in range(H)]

queue = deque([(y1-1, x1-1, 0)])
def bfs(queue):
    while queue:
        y, x, cnt = queue.popleft()
        if y==y2-1 and x==x2-1:
            return cnt
        if checked[y][x]>=1:
            continue
        checked[y][x]=cnt
        for dy, dx in dirc:
            for i in range(1, K+1):
                ny, nx = y+(dy*i), x+(dx*i)
                if ny>=H or ny<0 or nx>=W or nx<0:
                    continue
                if query[ny][nx]=='@':
                    break
                if checked[ny][nx]<0:
                    queue.append((ny, nx, cnt+1))
                elif checked[ny][nx]<=checked[y][x]:
                    break
    return -1

print(bfs(queue))


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from collections import deque
inf = 10**18
H, W, K = mapint()
y1, x1, y2, x2 = mapint()
query = [list(str(input())) for _ in range(H)]
dirc = [(0, 1), (-1, 0), (0, -1), (1, 0)]

checked = [[-1]*W for _ in range(H)]
checked[y1-1][x1-1] = 0

queue = deque([(y1-1, x1-1)])
def bfs(queue):
    while queue:
        y, x = queue.popleft()
        if y==y2-1 and x==x2-1:
            return checked[y][x]
        for dy, dx in dirc:
            for i in range(1, K+1):
                ny, nx = y+(dy*i), x+(dx*i)
                if ny>=H or ny<0 or nx>=W or nx<0:
                    continue
                if query[ny][nx]=='@':
                    break
                if checked[ny][nx]<0:
                    checked[ny][nx] = checked[y][x]+1
                    queue.append((ny, nx))
                elif checked[ny][nx]<=checked[y][x]:
                    break
    return -1

print(bfs(queue))
### BUGGY CODE ###

from collections import defaultdict
N,Q = map(int,input().split())
d = defaultdict(list)

for _ in range(N-1):
    a,b = map(int,input().split())
    d[a].append(b)
    d[b].append(a)

c = defaultdict(int)

for _ in range(Q):
    p,x = map(int,input().split())
    c[p] += x

ans = [0 for i in range(N)]
que = [(1,0,-1)]
while len(que)>0:
    tmp = []
    for v,x,par in que:
        x += c[v]
        ans[v-1] = str(x)
        for w in d[v]:
            if w != par:
                tmp.append((w,x,v))
    que = tmp

print(*ans)


### FIXED CODE ###

from collections import defaultdict
N,Q = map(int,input().split())
d = defaultdict(list)

for _ in range(N-1):
    a,b = map(int,input().split())
    d[a].append(b)
    d[b].append(a)

c = defaultdict(int)

for _ in range(Q):
    p,x = map(int,input().split())
    c[p] += x

ans = [0 for i in range(N)]
que = [(1,0,-1)]
while len(que)>0:
    tmp = []
    for v,x,par in que:
        x += c[v]
        ans[v-1] = str(x)
        for w in d[v]:
            if w != par:
                tmp.append((w,x,v))
    que = tmp

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

N,Q=map(int,input().split())
S=input()
ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
ABCD={}
for i,l in enumerate(ABC):
    ABCD[l]=i
    
memo=[[] for _ in range(26)]
for i,s in enumerate(S):
    memo[ABCD[s]].append(i)
state=[1]*N
exist=N

for _ in range(Q):
    t,d=input().split()
    
    if d=='L':
        tmp=memo[ABCD[t]][:]
        if tmp==[]: continue
        if tmp[0]==0:
            exist-=state[0]
            state[0]=0
            del tmp[0]
        for m in tmp:
            state[m-1]+=state[m]
            state[m]=0
    
    else:
        tmp=memo[ABCD[t]][::-1]
        if tmp==[]: continue
        if tmp[0]==N-1:
            exist-=state[-1]
            state[-1]=0
            del tmp[0]
        for m in tmp:
            state[m+1]+=state[m]
            state[m]=0
print(exist)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
TD=[tuple(input().split()) for _ in range(Q)]

def go(x):
    pos=x
    for t,d in TD:
        if pos==N: return N
        if pos==-1: return -1
        if t==S[pos]:
            if d=='L': pos-=1
            else: pos+=1
    return pos

U=N
L=-1
while U-L>1:
    x=(U+L)//2
    if go(x)==-1: L=x
    else: U=x
left=L

U=N
L=-1
while U-L>1:
    x=(U+L)//2
    if go(x)==N: U=x
    else: L=x
right=U

print(right-left-1)
### BUGGY CODE ###

from math import factorial
import collections


combs = {}
results = {}


def get_combination(n):
    if n < 2:
        return 0
    if combs.get(n):
        return combs.get(n)
    else:
        combs[n] = factorial(n) // (factorial(n - 2) * factorial(2))
        return combs[n]


n = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
S = 0
for k, v in c.items():
    S += get_combination(v)
for a in A:
    if results.get(a):
        print(results[a])
    else:
        results[a] = S - get_combination(c[a]) + get_combination(c[a] - 1)
        print(results[a])


### FIXED CODE ###

import collections
from functools import lru_cache
from scipy.misc import comb


results = {}


@lru_cache(maxsize=None)
def get_combination(n):
    if n < 2:
        return 0
    else:
        return comb(n, 2, exact=True)


n = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
S = 0
for k, v in c.items():
    S += get_combination(v)
for a in A:
    if results.get(a):
        print(results[a])
    else:
        results[a] = S - get_combination(c[a]) + get_combination(c[a] - 1)
        print(results[a])
### BUGGY CODE ###

n=int(input())
s=input()
import numpy as np

t=0
s_arr=np.array(list(s))
p=np.where(s_arr=='R')
R_ind=p[0]
p=np.where(s_arr=='G')
G_ind=p[0]
p=np.where(s_arr=='B')
B_ind=p[0]
k=len(B_ind)
len(R_ind)*len(G_ind)*len(B_ind)
for i in range(0,len(R_ind)):
    for j in range(0,len(G_ind)):
        r=R_ind[i]
        g=G_ind[j]
        m=abs(r-g)
        rb_diff=abs(B_ind-r)
        gb_diff=abs(B_ind-g)
        t=t+k-sum((rb_diff==m)*1+(gb_diff==m)*1+(rb_diff==gb_diff)*1)
print(t)


### FIXED CODE ###

n=int(input())
s=input()
p=s.count('R')*s.count('G')*s.count('B')

for i in range(0,n-2):
    for j in range(1,int((n-i)/2)+1):
        if i+j*2>=n:
            break
        if s[i]!=s[i+j] and s[i]!=s[i+j*2] and s[i+j*2]!=s[i+j]:
            p-=1
print(p)
### BUGGY CODE ###

a,b = map(int,input().split())
tower_list = [[1,3]]
for i in range(3,999):
    tower_list.append([tower_list[i-3][1],tower_list[i-3][1]+i])
i=0
while(True):
    ab_list = [a+i,b+i]
    if(ab_list in tower_list):
        print(i)
        exit()
    i += 1


### FIXED CODE ###

a,b = map(int,input().split())
print(int((b-a)*(b-a+1)/2-b))
### BUGGY CODE ###

import math

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

def honya(n, L):
  k = 0
  E = len(L)
  for i in range(n - 1, -1, -1):
    for j in range(k, E):
      if (L[j] >> i) & 1:
        L[k], L[j] = L[j], L[k]
        break
    else:
      continue
    k += 1
    for j in range(k, E):
      if (L[j] >> i) & 1:
        L[j] ^= L[k - 1]
  return L

def nasu(n):
  return math.ceil(math.log(n + 1, 2))

A.sort(reverse = True)
M = nasu(A[0])
P = [1]
for i in range(M):
  P.append(P[-1] * 2)

D = [0] * M
for i in range(N):
  t = A[i]
  for j in range(M):
    if t & 1:
      D[j] += 1
    t >>= 1

ans = 0
for i in range(M - 1, -1, -1):
  if D[i] % 2 == 1:
    ans += P[i]
    for j in range(N):
      A[j] &= ~(1 << i)

L = honya(M, A)
t = 0
for i in range(N):
  if L[i] == 0: break
  if (t & (1 << (nasu(L[i]) - 1))) == 0:
    t ^= L[i]

for i in  range(M - 1, -1, -1):
  if (t >> i) & 1:
    ans += P[i] * 2
    
print(ans)


### FIXED CODE ###

import math

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

def honya(n, L):
  k = 0
  E = len(L)
  for i in range(n - 1, -1, -1):
    for j in range(k, E):
      if (L[j] >> i) & 1:
        L[k], L[j] = L[j], L[k]
        break
    else:
      continue
    k += 1
    for j in range(k, E):
      if (L[j] >> i) & 1:
        L[j] ^= L[k - 1]
  return L

def nasu(n):
  return math.ceil(math.log(n + 1, 2))

A.sort(reverse = True)
M = nasu(A[0])
P = [1]
for i in range(M):
  P.append(P[-1] * 2)

D = [0] * M
for i in range(N):
  t = A[i]
  for j in range(M):
    if t & 1:
      D[j] += 1
    t >>= 1

ans = 0
for i in range(M - 1, -1, -1):
  if D[i] % 2 == 1:
    ans += P[i]
    for j in range(N):
      A[j] &= ~(1 << i)

L = honya(M, A)
t = 0
for i in range(N):
  if L[i] == 0: break
  if (t & (1 << (nasu(L[i]) - 1))) == 0:
    t ^= L[i]

for i in  range(M - 1, -1, -1):
  if (t >> i) & 1:
    ans += P[i] * 2
    
print(ans)
### BUGGY CODE ###

class SegmentTree():
    def segfunc(self, x, y):
        from fractions import gcd
        if x > y:
            x, y = y, x
        if x == -1:
            return y
        return gcd(x, y) #関数
    
    def __init__(self, a): #a:リスト
        n = len(a)
        self.ide_ele = -1 #単位元
        self.num = 2**((n-1).bit_length()) #num:n以上の最小の2のべき乗
        self.seg = [self.ide_ele]*2*self.num
        
        #set_val
        for i in range(n):
            self.seg[i+self.num-1] = a[i]
        #built
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])
        
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
            
    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q - p > 1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
    
N = int(input())
A = list(map(int, input().split()))
M = 0
for i in range(N):
    S = SegmentTree(A)
    S.update(i, -1)
    M = max(M, S.query(0,N))
print(M)

### FIXED CODE ###

class SegmentTree():
    def segfunc(self, x, y):
        if x > y:
            x, y = y, x
        if x == -1:
            return y
        return gcd(x, y) #関数
    
    def __init__(self, a): #a:リスト
        n = len(a)
        self.ide_ele = -1 #単位元
        self.num = 2**((n-1).bit_length()) #num:n以上の最小の2のべき乗
        self.seg = [self.ide_ele]*2*self.num
        
        #set_val
        for i in range(n):
            self.seg[i+self.num-1] = a[i]
        #built
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])
        
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
            
    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q - p > 1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
    
from fractions import gcd
    
N = int(input())
A = list(map(int, input().split()))
M = 0
S = SegmentTree(A)
for i in range(N):
    M = max(M, S.segfunc(S.query(0,i), S.query(i+1, N)))
print(M)
### BUGGY CODE ###

h, w, K = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]

def cumsum(s):
    n = len(s)
    cs = [0] * (n+1)
    for i in range(n):
        cs[i+1] = cs[i] + s[i]
    return cs
cums = [cumsum(c) for c in s]
ans = float("inf")    

for i in range(2 ** (h-1)):
    seps = [(i >> j) & 1 for j in range(h-1)] + [1]
    c = [[0] * (w+1) for _ in range(sum(seps))]
    idx = 0
    for j in range(h):
        for k in range(w+1):
            c[idx][k] += cums[j][k]
        if seps[j]: idx += 1
    
    flg = False
    for j in range(len(c)):
        for k in range(w):
            if c[j][k+1]-c[j][k] > K:
                flg = True
    if flg: continue                

    res = 0
    left = 0
    for j in range(w-1):
        for cc in c:
            if cc[j+2] - cc[left] > K:
                break
        else: continue
        res += 1
        left = j+1
    
    ans = min(ans, res+sum(seps)-1)

print(ans)


### FIXED CODE ###

h, w, K = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]

def cumsum(s):
    n = len(s)
    cs = [0] * (n+1)
    for i in range(n):
        cs[i+1] = cs[i] + s[i]
    return cs
cums = [cumsum(c) for c in s]
ans = float("inf")    

for i in range(2 ** (h-1)):
    seps = [(i >> j) & 1 for j in range(h-1)] + [1]
    c = [[0] * (w+1) for _ in range(sum(seps))]
    idx = 0
    for j in range(h):
        for k in range(w+1):
            c[idx][k] += cums[j][k]
        if seps[j]: idx += 1
    
    flg = False
    for j in range(len(c)):
        for k in range(w):
            if c[j][k+1]-c[j][k] > K:
                flg = True
    if flg: continue                

    res = 0
    left = 0
    for j in range(w-1):
        for cc in c:
            if cc[j+2] - cc[left] > K:
                break
        else: continue
        res += 1
        left = j+1
    
    ans = min(ans, res+sum(seps)-1)

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    a = [c if j == b else j for j in a]
    print(sum(a))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for i in range(q)]
l = [0] * 100000
suml = 0
for i in a:
  l[i-1] += 1
  suml += i
for i in bc:
  suml += l[i[0]-1] * (i[1] - i[0])
  l[i[1]-1] += l[i[0]-1]
  l[i[0]-1] = 0
  print(suml)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
D - Triangles
https://atcoder.jp/contests/abc143/tasks/abc143_d

"""
import sys

from itertools import combinations
from bisect import bisect_left, bisect_right

def solve(N, lines):
    ans = 0
    for c in range(N-1, -1, -1):
        for b in range(c-1, -1, -1):
            i = bisect_right(lines[:b], lines[c] - lines[b])
            ans += max(0, (b-i))
    return ans


def main(args):
    N = int(input())
    lines = map(int, input().split())
    ans = solve(N, sorted(lines))
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
D - Triangles
https://atcoder.jp/contests/abc143/tasks/abc143_d

"""
import sys

from itertools import combinations
from bisect import bisect_left, bisect_right

def solve(N, lines):
    ans = 0
    for c in range(N-1, -1, -1):
        for b in range(c-1, -1, -1):
            i = bisect_right(lines[:b], lines[c] - lines[b])
            ans += max(0, (b-i))
    return ans


def main(args):
    N = int(input())
    lines = map(int, input().split())
    ans = solve(N, sorted(lines))
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])