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

N,K,Q=list(map(int,input().split()))
A=[int(input()) for _ in range (Q)]
B=[0 for _ in range (N)]
for i in range(Q):
    B[A[i]-1]+=1
for i in range(N):
    if sum(B)-B[i]>=K:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

N,K,Q=list(map(int,input().split()))
A=[int(input()) for _ in range (Q)]
B=[0 for _ in range (N)]
for i in range(Q):
    B[A[i]-1]+=1
C=sum(B)-K
for i in range(N):
    if C>=B[i]:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

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

ans = 0
jyogai = 0

for i in range(N-1):
    nS = S[i+1:]
    kouho = []
    for w in ["R", "G", "B"]:
        if S[i] != w:
            kouho.append(nS.count(w))
    temp = i
    while True:
        temp += 1
        temp2 = temp - i
        if i + 2*temp2 > N-1:
            break
        b = [S[i], S[i + temp2], S[i + 2*temp2]]
        if len(set(b)) == 3:
            jyogai += 1

    ans += kouho[0] * kouho[1]

print(ans - jyogai)

### FIXED CODE ###

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

ans = 0
jyogai = 0

for i in range(N-1):
    nS = S[i+1:]
    kouho = []
    for w in ["R", "G", "B"]:
        if S[i] != w:
            kouho.append(nS.count(w))
    temp = i
    while True:
        temp += 1
        temp2 = temp - i
        if i + 2*temp2 > N-1:
            break
        b = [S[i], S[i + temp2], S[i + 2*temp2]]
        if len(set(b)) == 3:
            jyogai += 1

    ans += kouho[0] * kouho[1]

print(ans - jyogai)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

MAX=max(abs(A[0]),abs(A[-1]))
OK=-MAX**2-1
NG=MAX**2+1

import bisect

while NG-OK>1:
    mid=(OK+NG)//2
    SC=0
    for i in range(N):
        if A[i]>0:
            x=bisect.bisect_left(A,-(-mid//A[i]))
            SC+=max(0,x-i-1)

        elif A[i]<0:
            x=bisect.bisect_right(A,mid//A[i])
            SC+=min(N-i-1,N-x)
        else:
            if mid>0:
                SC+=N-i-1
            else:
                SC+=0
                
        if SC>=K:
            NG=mid
            break
    else:
        OK=mid
        
print(OK)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

M=[]
Z=[]
P=[]

for a in A:
    if a<0:
        M.append(-a)
    elif a==0:
        Z.append(a)
    else:
        P.append(a)

M.reverse()

MINUS=len(M)*len(P)
PLUS=len(P)*(len(P)-1)//2+len(M)*(len(M)-1)//2
ZERO=N*(N-1)//2-PLUS-MINUS

if MINUS<K and K<=MINUS+ZERO:
    print(0)
    sys.exit()

if K<=MINUS:
    OK=10**18
    NG=0

    while OK-NG>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(M)):
            while NOW>=0 and mid<M[i]*P[NOW]:
                NOW-=1
            ANS+=len(P)-NOW-1

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(-OK)

else:
    OK=0
    NG=10**18
    K-=MINUS+ZERO

    while NG-OK>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(P)):
            while NOW>0 and mid<=P[i]*P[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        NOW=len(M)-1

        for i in range(len(M)):
            while NOW>0 and mid<=M[i]*M[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(OK)
### BUGGY CODE ###

N,s = input().split()
S = int(s)
a = []
for i in range(int(N)):
    a.append(int(input()))

a.sort()

mindiff = 10000000000

for i in range(int(N)-(S - 1)):
    v = 0
    for j in range(int(S)-1):
        v += a[i+j+1]-a[i+j]
        if mindiff < v:break

    if mindiff > v: mindiff = v

print(mindiff)





### FIXED CODE ###

N,s = input().split()
S = int(s)
a = []
for i in range(int(N)):
    a.append(int(input()))

a.sort()

mindiff = 1000000000

for i in range(int(N)-(S - 1)):
    v = a[i+S-1]-a[i]

    if mindiff > v: mindiff = v

print(mindiff)
### BUGGY CODE ###

# This program computes GCD and LCM
# -*- coding: utf-8
import sys


def gcd(a, b):
    g = 1
    for i in range(1, max([a, b])):
        if(a % i == 0 and b % i == 0):
            g = i
    return g


def lcm(a, b):
    for i in range(max([a, b]), a*b + 1):
        if(i % a == 0 and i % b == 0):
            return i
    return a*b


for i in sys.stdin:
    try:
        line = [int(k) for k in i.split(" ")]
        print(str(gcd(line[0], line[1])) + " " + str(lcm(line[0], line[1])))
    except:
        exit()

### FIXED CODE ###

# This program computes GCD and LCM
# -*- coding: utf-8
import sys


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


for i in sys.stdin:
    try:
        line = [int(k) for k in i.split(" ")]
        g = gcd(min(line), max(line))
        print(str(g) + " " + str(line[0]*line[1]//g))
    except:
        exit()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)

points = [0]*N
for i in range(Q):
  p, x = map(int, input().split())
  points[p-1] += x
  
def dfs(v, pv):
  global points
  for nv in G[v]:
    if nv != pv:
      points[nv] += points[v]
      dfs(nv, v)

dfs(0, 0)
print(*points)

### FIXED CODE ###

#138_D
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 6)

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

edges = [[] for _ in range(n)]
cnt = [0 for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    
for _ in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x
    
def dfs(frm, cur):
    for to in edges[cur]:
        if to != frm:
            cnt[to] += cnt[cur]
            dfs(cur, to)
dfs(-1, 0)          
print(*cnt)
### BUGGY CODE ###

def search(l, n):
    left = 0
    right = len(l) - 1
    m = (left + right) // 2

    # while right - left > 1:
    while left < right:
        if n == l[m]:
            return True
        elif n < l[m]:
            right = m
        elif n > l[m]:
            left = m
        else:
            raise Exception()

        m = (left + right) // 2

    # if l[left] == n or l[right] == n:
    #     return True
    # else:
    #     return False


n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]

ans = 0
for ti in t:
    if search(s, ti):
        ans += 1

print(ans)



### FIXED CODE ###

def search(l, n):
    left = 0
    right = len(l) - 1
    while right - left > 1:
        m = (left + right) // 2
        if n == l[m]:
            return True
        elif n < l[m]:
            right = m
        else:
            left = m

    # print(left, right)
    if l[left] == n or l[right] == n:
        return True
    else:
        return False


n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]

ans = 0
for ti in t:
    if search(s, ti):
        ans += 1

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

ignore = int(raw_input())
k = map(int, raw_input().split())
copyk = list(set(k))
counter = 0

for i in xrange(len(copyk)):
    if (k.count(copyk[i]) > copyk[i]):
        counter+=k.count(copyk[i]) - copyk[i]
    if k.count(copyk[i]) < copyk[i]:
        counter+=k.count(copyk[i])

print counter


### FIXED CODE ###

from collections import Counter

ignore = int(raw_input())
k = dict(Counter(map(int, raw_input().split())))
copyk = list(set(k))
counter = 0
for i,j in k.items():
    if i > j:
        counter += j
    elif i < j:
        counter += j - i

print counter
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(M):
    B, C = map(int, input().split())
    A += [C] * B
A.sort()
A = A[-N:]
print(sum(A))

### FIXED CODE ###

import numpy as np
from collections import Counter

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = []
C = []
for _ in range(M):
    b1, c1 = map(int, input().split())
    B.append(b1)
    C.append(c1)

A = list(Counter(A).items())

for i in range(len(A)):
    C.append(A[i][0])
    B.append(A[i][1])
 
d = np.argsort(C)[::-1]
B = [B[i] for i in d]
C = [C[i] for i in d]

i = 0
c = 0
ans = 0
while True:
    if c + B[i] < N:
        ans += C[i] * B[i]
        c += B[i]
        i += 1
    else:
        ans += C[i] * (N - c)
        break
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)

n = int(input())
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in graph.items():
    if len(v) > _max:
        _max = len(v)
        _max_node = k
colors = [[0 for i in range(n)] for j in range(n)]
que = deque()
color_dict = {i : [] for i in range(n)}
cur = _max_node
while True:
    cnt = 1
    for _next in graph[cur]:
        if colors[cur][_next] == 0:
            que.append(_next)
            candidate = color_dict[_next] + color_dict[cur]
            while cnt in candidate:
                cnt = cnt + 1 if cnt + 1 <= _max else 1
            colors[cur][_next] = cnt
            colors[_next][cur] = cnt
            color_dict[cur].append(cnt)
            color_dict[_next].append(cnt)
            cnt += 1
    if len(que) == 0:
        break
    cur = que.popleft()
print(_max)
for a, b in ls:
    print(colors[a][b])

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)

n = int(input())
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in graph.items():
    if len(v) > _max:
        _max = len(v)
        _max_node = k

parent = [_max_node] * (n)
order = []
stack = [_max_node]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

colors = [-1 for i in range(n)]
for i in order:
    c = 1
    for _next in graph[i]:
        if _next == parent[i]:
            continue
        if c == colors[i]:
            c += 1
        colors[_next] = c
        c += 1
print(_max)
for a, b in ls:
    if parent[a] == b:
        print(colors[a])
    else:
        print(colors[b])
### BUGGY CODE ###

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

def lcm(a, b):
    return a * b // gcd(a, b)

mod = int(1e9 + 7)

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

l = a[0]
for i in range(1, n):
    l = lcm(l, a[i])

ans = 0
for i in range(n):
    ans = (ans + l // a[i]) % mod
print(ans)

### FIXED CODE ###

mod = int(1e9 + 7)

def inv(x):
    return pow(x, mod - 2, mod)

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

def lcm(a, b):
    return a * b // gcd(a, b)

def mod_lcm(a, b):
    return a * b % mod * inv(gcd(a, b)) % mod


while True:
    try:
        n = int(input())
        a = list(map(int, input().split()))
    except:
        break

    l = a[0]
    for i in range(1, n):
        l = lcm(l, a[i])
    l %= mod

    ans = 0
    for i in range(n):
        ans = (ans + l * inv(a[i])) % mod
    print(ans)
### BUGGY CODE ###

def main():
    from collections import namedtuple

    Ratio = namedtuple('Ratio', 'gold, silver copper')

    def trade(n, Rfrm, Rto):
        Df = Ratio(*(t - f for f, t in zip(Rfrm, Rto)))
        dp = [n] * (n + 1)
        for acorn in range(1, n + 1):
            dp[acorn] = max(
                dp[acorn],
                0 if acorn < Rfrm.gold else dp[acorn - Rfrm.gold] + Df.gold,
                0 if acorn < Rfrm.silver else dp[acorn - Rfrm.silver] + Df.silver,
                0 if acorn < Rfrm.copper else dp[acorn - Rfrm.copper] + Df.copper
            )
        return dp[n]

    n = int(input())
    Ra = Ratio(*map(int, input().split()))
    Rb = Ratio(*map(int, input().split()))

    ret = trade(n=n, Rfrm=Ra, Rto=Rb)
    ret = trade(n=ret, Rfrm=Rb, Rto=Ra)
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

# A : ドングリと金属に変える
# B : 全部ドングリに変える
# B : ドングリと金属に変える（無駄な操作でロスがないので、いったんドングリ化してよい）
# A : ドングリに変える

dp1 = list(range(N + 1))  # dp1[巣から持ってきたドングリ数] = 取引所 B で持てる最大ドングリ数
dp1[0] = 0
for i in range(N + 1):
    if i >= ga:
        dp1[i] = max(dp1[i], dp1[i - ga] + gb)
    if i >= sa:
        dp1[i] = max(dp1[i], dp1[i - sa] + sb)
    if i >= ba:
        dp1[i] = max(dp1[i], dp1[i - ba] + bb)

N = dp1[N]
dp2 = list(range(N + 1))  # dp2[取引所 B から持ってきたドングリ数] = 巣に持ち帰れる最大ドングリ数
for i in range(N + 1):
    if i >= gb:
        dp2[i] = max(dp2[i], dp2[i - gb] + ga)
    if i >= sb:
        dp2[i] = max(dp2[i], dp2[i - sb] + sa)
    if i >= bb:
        dp2[i] = max(dp2[i], dp2[i - bb] + ba)
print(dp2[N])
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
A = np.array(list(map(int, input().split())))
A.sort()
A = A[::-1]

# B, Cの結果を先にマージする
D = np.zeros((N, ), dtype='int')
for _ in range(M):
    D.sort()
    # print('sorted D', D)
    b, c = map(int, input().split())
    # print('bc', b, c)
    for i in range(min(b, len(D))):
        if D[i] < c:
            D[i] = c
        else:
            break
    # print('after D', D)
D.sort()
# print(D)
# print(A)
# print(np.maximum(D, A))
print(np.maximum(D, A).sum())


### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
A = np.array(list(map(int, input().split())))
A.sort()

# B, Cで出てくる数字全部並べて最後にsortしてAの数だけ取れば良さそう？
BC = []
for _ in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
BC = sorted(BC, key=lambda x: -x[1])

D = []
n = 0
for b, c in BC:
    if n + b >= N:
        while len(D) < N:
            D.append(c)
        break
    else:
        for i in range(b):
            D.append(c)
        n += b

while len(D) < N:
    D.append(0)

print(np.maximum(D, A).sum())
### BUGGY CODE ###

import numpy as np
n=int(input())
a=list(map(int,input().split()))
a1=[]
a2=[]
for i in range(n):
  a1.append(i+1-a[i])
for i in range(n):
  a2.append(i+1+a[i])
count=0
for k in range(n):
  for l in range(k-1):
    if a1[k]==a2[l]:
      count+=1
print(count)

### FIXED CODE ###

from collections import Counter
n=int(input())
alist=list(map(int,input().split()))
a1=[]
a2=[]
for i,a in enumerate(alist):
  a2.append(i-a)
  a1.append(i+a)
aa=Counter(a2)
count=0
for k in a1:
  count+=aa.get(k,0)
print(count)
### BUGGY CODE ###

N = int(input())
ans = 0
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]
for i in range(1,N):
    n = N - i
    m = len(make_divisors(n))
    ans += m
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1,N):
    x = (N-1)//i
    ans += x
print(ans)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
l,r=[],[]
for i in range(Q):
    l0,r0=map(int,input().split())
    l.append(l0)
    r.append(r0)
for i in range(Q):
    c=0
    for j in range(l[i]-1,r[i]-1):
        if (S[j]=='A') and (S[j+1]=='C'):
            c+=1
    print(c)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
t=[0]*N
for i in range(N-1):
    t[i+1]=t[i]+(1 if S[i:i+2]=='AC' else 0)
for i in range(Q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

H, W = map(int, input().split())
func = (lambda x: 1 if x == "#" else 0)
field = [[func(i) for i in input()] for _ in range(H)]
blackQ = []

for i, wField in enumerate(field):
    for j, w in enumerate(wField):
        if w == 1:
            blackQ.append((i, j))

ans = 0
while(True):
    bQ = []
    for _ in range(len(blackQ)):
        i, j = blackQ.pop()
        if i - 1 >= 0 and field[i-1][j] != 1:
            field[i-1][j] = 1
            bQ.append((i - 1, j))
        if i + 1 <= H - 1 and field[i+1][j] != 1:
            field[i+1][j] = 1
            bQ.append((i + 1, j))
        if j - 1 >= 0 and field[i][j-1] != 1:
            field[i][j-1] = 1
            bQ.append((i, j - 1))
        if j + 1 <= W - 1 and field[i][j + 1] != 1:
            field[i][j+1] = 1
            bQ.append((i, j + 1))

    if len(bQ) == 0:
        break

    ans += 1
    blackQ = bQ.copy()

print(ans)



### FIXED CODE ###

H, W = map(int, input().split())
func = (lambda x: 1 if x == "#" else 0)
field = [[func(i) for i in input()] for _ in range(H)]
blackQ = []

for i, wField in enumerate(field):
    for j, w in enumerate(wField):
        if w == 1:
            blackQ.append((i, j))

ans = 0
while(True):
    bQ = []
    for _ in range(len(blackQ)):
        i, j = blackQ.pop()
        if i - 1 >= 0 and field[i-1][j] != 1:
            field[i-1][j] = 1
            bQ.append((i - 1, j))
        if i + 1 <= H - 1 and field[i+1][j] != 1:
            field[i+1][j] = 1
            bQ.append((i + 1, j))
        if j - 1 >= 0 and field[i][j-1] != 1:
            field[i][j-1] = 1
            bQ.append((i, j - 1))
        if j + 1 <= W - 1 and field[i][j + 1] != 1:
            field[i][j+1] = 1
            bQ.append((i, j + 1))

    if len(bQ) == 0:
        break

    ans += 1
    blackQ = bQ

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

n= int(input())
l= list(map(int,input().split()))
pro = l[0]
for i in range(1,n):
    pro *= l[i]
if pro > 10**18:
        print('-1')
else:
    print(pro)

### FIXED CODE ###

n= int(input())
l= list(map(int,input().split()))
if 0 in l:
    print(0)
    exit()
pro = l[0]
for i in range(1,n):
    pro *= l[i]
    if pro > 10**18:
        print('-1')
        exit()
print(pro)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
for _ in range(M):
    b,c = list(map(int,input().split()))
    tmp = [c]*b
    A = A + tmp
A=sorted(A,reverse=1)[:N]
print(sum(A))


### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

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

import itertools


D, G = map(int, input().split())

P     = [None] * D
C     = [None] * D
count = [None] * D
score = [None] * D

for i in range(D):
    p, c          = map(int, input().split())
    P[i]          = p
    C[i]          = c
    count[i]      = list(range(p+1))
    score[i]      = [100 * (i+1) * j for j in range(p+1)]
    score[i][-1] += c

answer = sum(P)

for is_complete in itertools.product([True, False], repeat=D):
    score_tmp  = 0
    count_tmp  = 0
    score_tmp += sum([score[i][-1] for i in range(D) if is_complete[i]])
    count_tmp += sum([count[i][-1] for i in range(D) if is_complete[i]])
    while score_tmp < G:
        for i in list(range(D))[::-1]:
            if is_complete[i] == False:
                if (G - score_tmp) % (100 * (i+1)) == 0:
                    count_add  = min((G - score_tmp) // (100 * (i+1)),     P[i] - 1)
                else:
                    count_add  = min((G - score_tmp) // (100 * (i+1)) + 1, P[i] - 1)
                score_add      = 100 * (i+1) * count_add
                count_tmp     += count_add
                score_tmp     += score_add
            if score_tmp >= G:
                break
    if score_tmp >= G:
        answer = min(answer, count_tmp)

print(answer)


### FIXED CODE ###

import itertools


D, G = map(int, input().split())

P     = [None] * D
C     = [None] * D
count = [None] * D
score = [None] * D

for i in range(D):
    p, c          = map(int, input().split())
    P[i]          = p
    C[i]          = c
    count[i]      = list(range(p+1))
    score[i]      = [100 * (i+1) * j for j in range(p+1)]
    score[i][-1] += c

answer = sum(P)

for is_complete in itertools.product([True, False], repeat=D):
    score_tmp  = 0
    count_tmp  = 0
    score_tmp += sum([score[i][-1] for i in range(D) if is_complete[i]])
    count_tmp += sum([count[i][-1] for i in range(D) if is_complete[i]])
    if score_tmp < G:
        for i in list(range(D))[::-1]:
            if is_complete[i] == False:
                if (G - score_tmp) % (100 * (i+1)) == 0:
                    count_add  = min((G - score_tmp) // (100 * (i+1)),     P[i] - 1)
                else:
                    count_add  = min((G - score_tmp) // (100 * (i+1)) + 1, P[i] - 1)
                score_add      = 100 * (i+1) * count_add
                count_tmp     += count_add
                score_tmp     += score_add
            if score_tmp >= G:
                break
    if score_tmp >= G:
        answer = min(answer, count_tmp)

print(answer)
### BUGGY CODE ###

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

ans=0

for n in range(0,N-2):
    for o in range(n+1, N-1):
        for p in range(o+1, N):
            if (L[n] < L[o] + L[p]) and (L[o] < L[p] + L[n]) and (L[p] < L[n] + L[o]):
                ans += 1
                
print(int(ans))


### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L = sorted(L)

count = 0
for n in range(N-2):
    for m in range(n+1,N-1):
        count += bisect.bisect_left(L,L[m]+L[n]) -m-1

print(count)
### BUGGY CODE ###

import sys
from operator import itemgetter
input = sys.stdin.readline

_n = int(input())
lrlist, Lp, Rq = [], 0, 10 ** 9
for _ in range(_n):
    l, r = map(int, input().split())
    lrlist.append((l, r))
    Lp, Rq = max(Lp, l), min(Rq, r)

st = sorted([(max(r - Lp + 1, 0), max(Rq - l + 1, 0)) for l, r in lrlist], key=itemgetter(0))

ans = max([r - l + 1 for l, r in lrlist]) + max(Rq - Lp + 1, 0)
for i in range(1, _n):
    s, t = st[:i], st[i:]
    min_b, min_a = sorted(s, key=itemgetter(1))[0][1], t[0][0]

    ans = max(min_a + min_b, ans)

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

_n = int(input())
lrlist = [list(map(int, input().split())) for _ in range(_n)]
Lp, Rq = max(l for l, r in lrlist), min(r for l, r in lrlist)

st = sorted([(max(r - Lp + 1, 0), max(Rq - l + 1, 0)) for l, r in lrlist], key=lambda x: (x[0], -x[1]))
ans = max([r - l + 1 for l, r in lrlist]) + max(Rq - Lp + 1, 0)

min_b = 10 ** 9
for i in range(_n - 1):
    min_b = min(st[i][1], min_b)
    ans = max(ans, min_b + st[i + 1][0])

print(ans)