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

N = int(input())

NGlist = [0] * N
grouplist = [0]*N
ans = 0
for i in range(N):
    NGlist[i] = [0] * N
    grouplist[i] = [0] * N


for k in range(N):
    n = int(input())
    for j in range(n):
        x, y = map(int, input().split())
        if y == 0:
            NGlist[k][x-1] = 1
            NGlist[x - 1][k] = 1
        if y == 1:
            grouplist[k][x-1] = 1

for num in range(2 ** N):
    # print("num=")
    # print(num)
    group = set()
    newmember = set()
    for h in range(N):
        if h not in group and num % 2 == 1:
            group.add(h)
            newmember.add(h)
        num //= 2

    while (len(newmember) != 0):
        for s in list(newmember):
            for p in range(N):
                if grouplist[s][p] == 1 and p not in group:
                    group.add(p)
                    newmember.add(p)
                newmember.discard(s)

    len_group = len(group)
        # print(group)
    flag = 0
    if ans >= len_group:
       flag = 1
    
    # print(group)
    for m in group:
        for t in group:
            if NGlist[m][t] == 1:
                flag = 1
                break
        if flag == 1:
            break
    if flag == 0 and ans < len_group:
        ans = len_group

print(ans)


### FIXED CODE ###

N = int(input())

NGlist = [0] * N
grouplist = [0]*N
ans = 0
for i in range(N):
    NGlist[i] = [0] * N
    grouplist[i] = [0] * N


for k in range(N):
    n = int(input())
    for j in range(n):
        x, y = map(int, input().split())
        if y == 0:
            NGlist[k][x-1] = 1
            NGlist[x - 1][k] = 1
        if y == 1:
            grouplist[k][x-1] = 1

for num in range(2 ** N):
    # print("num=")
    # print(num)
    group = set()
    newmember = set()
    for h in range(N):
        if h not in group and num % 2 == 1:
            group.add(h)
            newmember.add(h)
        num //= 2

    while (len(newmember) != 0):
        for s in list(newmember):
            for p in range(N):
                if grouplist[s][p] == 1 and p not in group:
                    group.add(p)
                    newmember.add(p)
                newmember.discard(s)

    len_group = len(group)
        # print(group)
    flag = 0
    if ans >= len_group:
       flag = 1
    
    # print(group)
    for m in group:
        for t in group:
            if NGlist[m][t] == 1:
                flag = 1
                break
        if flag == 1:
            break
    if flag == 0 and ans < len_group:
        ans = len_group

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

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

cnt = [[[0, 0] for _ in range(n + 1)] for _ in range(60)]
for i in range(60): # <= 2^60
    for j, v in enumerate(a):
        if v & (1 << i):
            cnt[i][j][1] = cnt[i][j - 1][1] + 1
            cnt[i][j][0] = cnt[i][j - 1][0]
        else:
            cnt[i][j][1] = cnt[i][j - 1][1]
            cnt[i][j][0] = cnt[i][j - 1][0] + 1

result = 0
for p, delete in enumerate(a):
    for i, cs in enumerate(cnt):
        if delete & (1 << i):
            target = 0
        else:
            target = 1

        result += (cs[n - 1][target] - cs[p - 1][target]) * (1 << i)
print(result % (10**9 + 7))


### FIXED CODE ###

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

cnt = [[0, 0] for _ in range(60)]
for i in range(60): # <= 2^60
    for j, v in enumerate(a):
        cnt[i][bool(v & (1 << i))] += 1


# print(cnt[:5])
sub = [[0, 0] for _ in range(60)]

# "001"
# "010"
# "011"

result = 0
for i, c in enumerate(cnt):
    for j, delete in enumerate(a[:-1]):
        target = not (delete & (1 << i))
        result += (c[target] - sub[i][target]) * (1 << i)

        # print(i, ":", int(target), c[target], result, sub[i], "->", sub[i][target])

        sub[i][not target] += 1

    # print(result)
    # print("-----")
    # if i > 5: break

# print(result)


# for p, delete in enumerate(a):
#     for i, cs in enumerate(cnt):
#         if delete & (1 << i):
#             target = 0
#         else:
#             target = 1
#
#         result += (cs[n - 1][target] - cs[p - 1][target]) * (1 << i)
print(result % (10**9 + 7))
### BUGGY CODE ###

n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        if mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
start=input()
bin(start)


### FIXED CODE ###

import sys
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        elif mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
start=input()
sys.stdout.flush()
if start=='Vacant':exit()
bin(start)
### BUGGY CODE ###

from collections import deque
a = input()
q = int(input())
key = [0]*len(a)
for i in range(len(a)):
    key[i] = a[i]

p = deque(key)
for i in range(q):
    qinput = [str(x) for x in input().split()]
    if len(qinput) == 1:
        p.reverse()
    else:
        k = qinput[1]
        if k == "1":
            p.appendleft(qinput[2])
        else:
            p.append(qinput[2])
print("".join(p))

### FIXED CODE ###

from collections import deque
a = input()
q = int(input())
key = [0]*len(a)
for i in range(len(a)):
    key[i] = a[i]

p = deque(key)
rev = False
for i in range(q):
    qinput = [str(x) for x in input().split()]
    if len(qinput) == 1:
        if rev:
            rev = False
        else:
            rev = True
    else:
        k = qinput[1]
        if k == "1":
            if rev:
                p.append(qinput[2])
            else:
                p.appendleft(qinput[2])
        else:
            if not rev:
                p.append(qinput[2])
            else:
                p.appendleft(qinput[2])
if rev:
    p.reverse()
print("".join(p))
### BUGGY CODE ###

N = int(input())
A = []
for _ in range(N):
    a = int(input())
    if a in A:
        A.remove(a)
    else:
        A.append(a)
print(len(A))

### FIXED CODE ###

N = int(input())
dict = {}
for _ in range(N):
    a = int(input())
    if a in dict:
        dict[a] += 1
    else:
        dict[a] = 1

ans = 0
for v in dict.values():
    if v % 2 != 0:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys, re

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
#INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

def main():
	N, K = MAP()
	S = input()

	flg = [int(S[0])]
	count = []
	cnt = 1
	tmp = S[0]

	for x in S[1:]:
		if x == tmp:
			cnt += 1
		else:
			tmp = x
			flg.append(int(tmp))
			count.append(cnt)
			cnt = 1
	count.append(cnt)

	ans = 0
	for i in range(len(flg)):
		if flg[i]:
			ans = max(ans, sum(count[i:i+2*K+1]))
		else:
			ans = max(ans, sum(count[i:i+2*K]))

	print(ans)

if __name__ == '__main__':
	main()


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
#INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, K = MAP()
S = [int(s) for s in input()] + [1]

r = -1
ans = 0
cnt = 0
used = [0]*(N+1)

for l in range(N):
	if S[l] + S[l-1] == 0:
		continue
	while r < N and used[r] - used[l-1] <= K:
		r += 1
		if S[r-1] == 1 and S[r] == 0:
			used[r] = used[r-1] + 1
		else:
			used[r] = used[r-1]
	ans = max(ans, r-l)

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

N = int(input())

# (x + y) ** 2 = x2 + 2xy + y2
# (y + z) ** 2 = y2 + 2yz + z2
# (z + x) ** 2 = z2 + 2zx + x2
# 右辺 2(x2 + y2 + z2 + xy + yz + zx)
# よって (x + y) ** 2 + (y + z) ** 2 + (z + x) ** 2 = 2 * n

# x**2 + y**2 + z**2 + xy + yz + zx = n

# x = y = 1, N = 10**4の時のZは大きくて100なので100まで回せばよい
# 4 + 2(z**2 + 2z + 1) = 2 * 10**4
# 2 + z ** 2 + 2z + 1 = 10**4
# z(z + 2) = 10 ** 4 - 3
# 時間がかかりすぎるからx,y,zの値によって+1, +3, +6する 3C3, 3C2, 3C1


def f1(x, y, z):
    return (x + y)**2 + (y + z)**2 + (z + x)**2


# F = [0] * (10**4 + 1)
# F = [0] * (N + 1)
# for i in range(1, 10**4 + 1):
for i in range(1, N + 1):
    f = 0
    # for i in range(83, N + 1):
    right = 2 * i
    # print(f'{i=}')
    for x in range(1, 101):
        if f1(x, 1, 1) > right:
            break
        for y in range(x, 101):
            if f1(x, y, 1) > right:
                break

            for z in range(y, 101):
                # print(f'{i=}, {x=}, {y=}, {z=}')
                left = f1(x, y, z)
                if left > right:
                    break
                if left == right:
                    # print(f'{i=}, {x=}, {y=}, {z=}')
                    if x == y == z:
                        # F[i] += 1
                        f += 1
                    elif x == y or y == z or z == x:
                        # F[i] += 3
                        f += 3
                    else:
                        # F[i] += 6
                        f += 6
    print(f)
# print(f'{F=}')


### FIXED CODE ###

N = int(input())

# (x + y) ** 2 = x2 + 2xy + y2
# (y + z) ** 2 = y2 + 2yz + z2
# (z + x) ** 2 = z2 + 2zx + x2
# 右辺 2(x2 + y2 + z2 + xy + yz + zx)
# よって (x + y) ** 2 + (y + z) ** 2 + (z + x) ** 2 = 2 * n

# x**2 + y**2 + z**2 + xy + yz + zx = n

# x = y = 1, N = 10**4の時のZは大きくて100なので100まで回せばよい
# 4 + 2(z**2 + 2z + 1) = 2 * 10**4
# 2 + z ** 2 + 2z + 1 = 10**4
# z(z + 2) = 10 ** 4 - 3
# 時間がかかりすぎるからx,y,zの値によって+1, +3, +6する 3C3, 3C2, 3C1


def f1(x, y, z):
    return (x + y)**2 + (y + z)**2 + (z + x)**2


# F = [0] * (10**4 + 1)
# F = [0] * (N + 1)
# for i in range(1, 10**4 + 1):
for i in range(1, N + 1):
    f = 0
    # for i in range(83, N + 1):
    right = 2 * i
    # print(f'{i=}')
    for x in range(1, 101):
        if f1(x, 1, 1) > right:
            break
        for y in range(x, 101):
            if f1(x, y, 1) > right:
                break

            for z in range(y, 101):
                # print(f'{i=}, {x=}, {y=}, {z=}')
                left = f1(x, y, z)
                if left > right:
                    break
                if left == right:
                    # print(f'{i=}, {x=}, {y=}, {z=}')
                    if x == y == z:
                        # F[i] += 1
                        f += 1
                    elif x == y or y == z or z == x:
                        # F[i] += 3
                        f += 3
                    else:
                        # F[i] += 6
                        f += 6
    print(f)
# print(f'{F=}')
### BUGGY CODE ###

from operator import mul
from functools import reduce

MOD = 1000000007

mod_mul = lambda a,b:(a*b)%MOD

def cmb(n,r):
  r = min(n-r,r)
  if r < 0: return 0
  if r == 0: return 1

  over = reduce(mul, range(n, n - r, -1))
  under = reduce(mul, range(1,r + 1))
  return over // under

def solve():
  N = int(input())
  A = list(map(int, input().split()))
  counter = [-1]*(N+2)
  multi_num = -1
  left_element_num = -1
  right_element_num = -1
  for i, a_i in enumerate(A):
    if counter[a_i] != -1:
      left_element_num = counter[a_i]
      right_element_num = N-i
      break
    else:
      counter[a_i] = i

  # print(left_element_num, right_element_num)
  for i in range(1, N+2):
    if i == 1:
      print(N)
    elif i == N+1:
      print(1)
    else:
      ret = cmb(N+1, i)%MOD
      ret = (ret-cmb(left_element_num+right_element_num, i-1)%MOD)%MOD
      print(ret)
      
solve()

### FIXED CODE ###

MOD = 1000000007

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % MOD

MOD = 10**9+7 #出力の制限
MAX_N = 10**5+10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, MAX_N + 1 ):
    g1.append( ( g1[-1] * i ) % MOD )
    inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )
    g2.append( (g2[-1] * inverse[-1]) % MOD )

# 鳩ノ巣原理より重複する数が唯一つ存在する
# a_1,a_2,...,a_m,...,a_l,a_l+1,...,a_n
# 左サイドの個数をx,右サイドサイドの個数をyとしたら
# k番目の出力で重複する組合せは(x+y)から(k-1)選んだもの

def solve():
  N = int(input())
  A = list(map(int, input().split()))
  counter = [-1]*(N+2)
  multi_num = -1
  left_element_num = -1
  right_element_num = -1
  for i, a_i in enumerate(A):
    if counter[a_i] != -1:
      left_element_num = counter[a_i]
      right_element_num = N-i
      break
    else:
      counter[a_i] = i

  # print(left_element_num, right_element_num)
  output = []
  for i in range(1, N+2):
    if i == 1:
      output.append(str(N))
      # print(N)
    elif i == N+1:
      output.append(str(1))
      # print(1)
    else:
      ret = cmb(N+1, i)%MOD
      ret = (ret-cmb(left_element_num+right_element_num, i-1)%MOD)%MOD
      output.append(str(ret))
  
  print('\n'.join(output))
  
solve()
### BUGGY CODE ###

N, M = map(int, input().split())
X = list(sorted(map(int, input().split())))
if N >= M:
  print('0')
else:
  d = []
  for i in range(M - 1):
    d.append(X[i + 1] - X[i])
  for j in range(N - 1):
    d.remove(max(d))
  print(sum(d))

### FIXED CODE ###

N, M = map(int, input().split())
X = list(sorted(map(int, input().split())))
if N >= M:
  print('0')
else:
  d = []
  ans = X[-1] - X[0]
  for i in range(M - 1):
    d.append(X[i + 1] - X[i])
  ans -= sum(list(sorted(d, reverse=True))[0:N - 1])
  print(ans)
### BUGGY CODE ###

import bisect
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
d.sort();t.sort()

for i in range(m):
    b2=bisect.bisect_right(d,t[i])
    #print(d,t,b2)
    if d[b2-1]!=t[i]:
        print('NO')
        break
    else:
        d=d[:b2-1]+d[b2:]
else:
    print('YES')

### FIXED CODE ###

from collections import Counter
n=int(input())
d=Counter(map(int,input().split()))
m=int(input())
t=Counter(map(int,input().split()))
for i in t.keys():
    if d[i]<t[i]:
        print('NO')
        break
else:
    print('YES')
### BUGGY CODE ###

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

sum=0
for i in range(n):
    for j in range(i):
        sum+=a[i]*a[j]

ans=sum%(10**9+7)

print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
x=sum(a)
y=0
for i in range(n):
    y+=a[i]**2

ans = (x**2 - y)//2

ans = ans % (10**9+7)

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

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

for i in range(K):
  R = [ {} for j in range(N)]

  for j in range(N):
    s = A[j]
    # j - s ~ j + s
    if min(j+s, N-1) in R[max(0, j-s)]:
      R[max(0, j-s)][min(j+s, N-1)] += 1
    else:
      R[max(0, j-s)][min(j+s, N-1)] = 1
        
  # Make Next List
  #print(R)
  B = [0 for j in range(N)]
  L = [0 for j in range(N)]
  t = 0
  for j in range(N):
    r = R[j]
    for k, v in r.items():
      t += v
      L[k] += v
    B[j] = t
    t -= L[j]
    
  #Merge
  A = [ B[j] for j in range(N)]
  for j in range(N):
    if A[j] < N:
      break
  else:
    break
print(*A)

### FIXED CODE ###

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

for i in range(K):
  R = [ {} for j in range(N)]

  for j in range(N):
    s = A[j]
    # j - s ~ j + s
    if min(j+s, N-1) in R[max(0, j-s)]:
      R[max(0, j-s)][min(j+s, N-1)] += 1
    else:
      R[max(0, j-s)][min(j+s, N-1)] = 1
        
  # Make Next List
  #print(R)
  L = [0 for j in range(N)]
  t = 0
  for j in range(N):
    r = R[j]
    for k, v in r.items():
      t += v
      L[k] += v
    A[j] = t
    t -= L[j]
    
  if A[0] == N and A[-1] == N:
    for j in range(N):
      if A[j] < N:
        break
    else:
      break
print(*A)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
P = []
S = []


def f(s):
  lst = s.split()
  return int(lst[0]),lst[1]

for i in range(M):
  p, s = f(input())
  P.append(p)
  S.append(s)

correct = 0
penalty = 0
q = []
p = []

for i, j in enumerate(S):
  if 'AC' in j:
    if P[i] not in q:
      q.append(P[i])
      correct += 1
    else:
      q.append(P[i])
      continue
  if 'WA' in j:
    p.append(P[i])
    if P[i] not in q:
        penalty += 1
    else:
      continue
for i in range(len(p)):
  if p[i] not in q:
    penalty -= 1

print(correct, penalty)


### FIXED CODE ###


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

isAC = [0] * (N+1)
isWA = [0] * (N+1)

ACnum = 0
WAnum = 0

for _ in range(M):
    p, s = input().split()
    p = int(p)

    if isAC[p] == 1: continue
    if s == 'AC':
        isAC[p] = 1
        ACnum += 1
        WAnum += isWA[p]
    elif s == 'WA':
        isWA[p] += 1

print("%d %d"%(ACnum, WAnum))
### BUGGY CODE ###

N = int(input())
S = list(input())
min = N - 1
for i in range(N-1):
  cnt = S[:i].count('W') + S[i+1:].count('E')
  if cnt < min:
    min = cnt
print(min)

### FIXED CODE ###

N = int(input())
S = list(input())
W = 0
E = S[1:].count('E')
Turn = []
Turn.append(E)

for i in range(1, N):
  if S[i] == 'E':
    E -= 1
  if S[i-1] == 'W':
    W += 1
  Turn.append(E+W)

print(min(Turn))
### BUGGY CODE ###

def openinput():
    n, m = map(int, input().split())
    edges = [[] for _ in range(m)]
    for _ in range(m):
        si, ti = map(int, input().split())
        edges[si-1].append(ti-1)
    return n, m, edges

def to_n_expected(edges, num_of_nodes, recursive_depth=0):
    dp_table = [0]*num_of_nodes

    recursive_shotest = float('inf')
    for v in reversed(range(n-1)):
        if recursive_depth < 1:
            max_next = max(edges[v], key= lambda x: dp_table[x])
            edges[v].remove(max_next)
            expected = to_n_expected(edges, num_of_nodes, recursive_depth=1)
            edges[v].append(max_next)
            recursive_shotest = min(expected, recursive_shotest)
        
        num_of_nexts = len(edges[v])
        if num_of_nexts > 0:
            dp_table[v] = 1 + sum(dp_table[ne] for ne in edges[v]) / num_of_nexts
        else:
            dp_table[v] = float('inf')
    return min(dp_table[0], recursive_shotest)

if __name__ == '__main__':
    n, m, edges = openinput()
    expcted_values = to_n_expected(edges, n)
    print(expcted_values)

### FIXED CODE ###

# reference: https://www.onakasuitacity.com/abc144-f/

import numpy as np

n, m = map(int, input().split())
outgoing = [[] for _ in range(n)]
incoming = [[] for _ in range(n)]
for _ in range(m):
    si, ti = map(int, input().split())
    outgoing[si-1].append(ti-1)
    incoming[ti-1].append(si-1)


ex_dp = np.zeros(n)
for v in reversed(range(n-1)):   # O(m)
    outgoing_degree = len(outgoing[v])
    ex_dp[v] = 1 + sum(ex_dp[post] for post in outgoing[v])/outgoing_degree if outgoing_degree!=0 else np.inf

p_dp = np.ones(n)
for v in range(1,n):      # O(m)
    p_dp[v] = sum(p_dp[prev]/len(outgoing[prev]) for prev in incoming[v])

min_ex = ex_dp[0]
for v, posts in enumerate(outgoing):      # O(m)
    outgoing_degree = len(outgoing[v])
    if outgoing_degree <= 1:
        continue

    max_post = max(posts, key= lambda pos: ex_dp[pos])
    diff_v_ex = 0
    for w in posts:
        if w == max_post:
            diff_v_ex -= 1/outgoing_degree * ex_dp[w]
        else:
            diff_v_ex += 1/(outgoing_degree*(outgoing_degree-1)) * ex_dp[w]
    min_ex = min(ex_dp[0] + p_dp[v] * diff_v_ex, min_ex)

print(min_ex)
### BUGGY CODE ###

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]


N = int(input())

out=0
for i in range(1,N+1):
    out+=i * len(make_divisors(i))
print(out)

### FIXED CODE ###

N = int(input())

yaku = [0]*(N+1)
for i in range(1,N+1):
    yaku[i] = ((N//i)/2) * (2*i + ((N//i)-1)*i)

print(int(sum(yaku)))
### BUGGY CODE ###

from itertools import accumulate
N=int(input())
t=[]
s=list(map(int,input().split()))
for i in range(2,N-1):
    p=10**9
    for j in range(1,len(s[:i])):
        a=sum(s[:i][:j])
        b=sum(s[:i][j:])
        q=abs(a-b)
        if p>q:
            p=q
            (x,y)=(a,b)
    p=10**9        
    for j in range(1,len(s[i:])):
        a=sum(s[i:][:j])
        b=sum(s[i:][j:])
        q=abs(a-b)
        if p>q:
            p=q
            (x1,y1)=(a,b)
    l=(x,y,x1,y1)
    t.append(max(l)-min(l))
print(min(t))    

### FIXED CODE ###

from itertools import accumulate
N=int(input())
s=list(accumulate(map(int,input().split())))
ans=10**9
p=0
q=2
for i in range(2,N-1):
    while p<i-1 and abs(s[i-1]-2*s[p+1])<abs(s[i-1]-2*s[p]):
        p+=1
    if q<i:
        q+=1
    while q<N and abs(s[i-1]-2*s[q+1]+s[-1])<abs(s[i-1]-2*s[q]+s[-1]):   
        q+=1
    t=[s[q]-s[i-1],s[-1]-s[q],s[p],s[i-1]-s[p]]
    w=max(t)-min(t)
    ans=min(ans,w) 
print(ans)
### BUGGY CODE ###

from math import sqrt
from fractions import gcd
from collections import defaultdict
from copy import deepcopy

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

def f(n):
    d = defaultdict(int)
    for i in range(2,int(sqrt(n))+1):
        if n % i == 0:
            r = 0
            while n % i == 0:
                n //= i
                r += 1
            d[i] = r
    if n != 1:
        d[n] = 1
    return d

B = []
for i in range(N):
    B.append(f(A[i]))

lp = deepcopy(B[0])

for i in range(N-1):
    for j in list(set(B[i+1].keys()) | set(lp.keys())):
        lp[j] = max(B[i+1][j],lp[j])

ans = 0

for i in range(N):
    r = 1
    for j in list(lp.keys()):
        r = (r*pow(j,lp[j]-B[i][j],mod)) % mod
    ans = (ans + r) % mod

print(ans)

### FIXED CODE ###

def main():
    from math import sqrt
    from fractions import gcd
    from collections import defaultdict
    from copy import deepcopy

    N = int(input())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    p = [1] * (1001)
    P = []  # 1000までの素数表
    p[0] = p[1] = 0
    for x in range(2, int(sqrt(1000000)) + 1):
        if p[x]:
            P.append(x)
            for y in range(x * x, 1001, x):
                p[y] = 0

    B = [defaultdict(int) for i in range(N)]  # N個の数を素因数分解したもの
    lcm = defaultdict(int)  # N個の数のlcmを素因数分解したもの

    for i in range(N):
        for j in P:
            if A[i] % j == 0:
                while A[i] % j == 0:
                    A[i] //= j
                    B[i][j] += 1
            lcm[j] = max(lcm[j], B[i][j])
        if A[i] != 1:
            B[i][A[i]] = 1
            lcm[A[i]] = 1

    l = 1  # N個の数のlcm
    for i in lcm.keys():
        l = (l * pow(i, lcm[i], mod)) % mod

    ans = 0
    # l/A[i]の和を求めていく
    for i in range(N):
        r = l
        for j in list(B[i].keys()):
            r = (r * pow(j, mod - B[i][j] - 1, mod)) % mod
        ans = (ans + r) % mod

    print(ans)

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

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

for i in range(a,b+1):
    if i <= a+k-1 or i >= b-k+1: print(i) 

### FIXED CODE ###

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

for i in range(a,min(a+k,b+1)):
    print(i)

for i in range(max(a+k,b+1-k),b+1):
    print(i)
### BUGGY CODE ###

n,q= map(int,input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]

import numpy as np
for i,j in lr:
  print(s[i-1:j].count("AC"))

### FIXED CODE ###

n,q= map(int,input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
import numpy as np
sn = list(np.cumsum([0] + [s[i:i++2]=="AC" for i in range(n-1)]))

for i,j in lr:
  i -= 1
  j -= 1
  print(sn[j] - sn[i])