Harryxun/stf_run huggingface dataset:
import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    sn=pk[0]+n-pk[1]
    for i in range(n):
        ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
        ans1[i+1]=ans0[i]*2-(sn>i)*(fact[sn]*ifact[sn-i]*ifact[i] % p)
        ans2[i+2]=ans0[i]import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    sn=pk[0]+n-pk[1]
    for i in range(0,n+2):
        if i<n:
            ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
            ans1[i+1]=ans0[i]*2-(sn>=i)*(fact[sn]*ifact[sn-i]*ifact[i] % p)
            ans2[i+2]=ans0[i]
        if i>0:
            print((ans0[i]+ans1[i]+ans2[i]) % p)

if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
finput=lambda:sys.stdin.readline().strip()

def main():
    p=10**9+7
    n=int(finput())
    a=list(map(int,finput().split()))
    k=sum(a)-(n*(n+1))//2
    pk=[i for i in range(n+1) if a[i]==k]
    fact=[1]*(n+2)
    ifact=[1]*(n+2)
    for i in range(1,n+2):
        fact[i]=fact[i-1]*i % p
    a=fact[-1]
    inv=1
    m=p-2
    while m>0:
        if m&1:
            inv=a*inv % p
        m>>=1
        a=a*a % p
    ifact[-1]=inv
    for i in range(n+1,0,-1):
        ifact[i-1]=ifact[i]*i % p
    ans0=[0]*(n+2)
    ans1=[0]*(n+2)
    ans2=[0]*(n+2)
    for i in range(n):
        ans0[i]=fact[n-1]*ifact[n-i-1]*ifact[i]%p
        ans1[i+1]=ans0[i]*2
        ans2[i+2]=ans0[i]
    sn=pk[0]+n-pk[1]
    for i in range(sn+1):
        ans1[i+1]-=fact[sn]*ifact[sn-i]*ifact[i] % p
    for i in range(1,n+2):
        print((ans0[i]+ans1[i]+ans2[i]) % p)

if __name__=='__main__':
    main()
A,B,K = map(int,input().split())

def eat_cookie(A,B,K):
    if A == 0 && B == 0:
        return 0,0
    if A >= K:
        return A-K,B
    else:
        if B-A+k > 0:
            return 0,B-K+A
        else:
            return 0,0


resultA,resultB = eat_cookie(A,B,K)
print(resultA,resultB)


### FIXED CODE ###

A,B,K = map(int,input().split())

def eat_cookie(A,B,K):
    if A >= K:
        return A-K,B
    else:
        if B-K+A > 0:
            return 0,B-K+A
        else:
            return 0,0


resultA,resultB = eat_cookie(A,B,K)
print(resultA,resultB)
from collections import Counter
n=int(input())
balls=[]
distance=[]
for i in range(n):
  balls.append(list(map(int,input().split())))
for i in range(n-1):
  for j in range(i+1,n):
    distance.append(str(balls[i][0]-balls[j][0])+" "+str(balls[i][1]-balls[j][1]))
d=Counter(distance)
print(n-d.most_common()[0][1])


### FIXED CODE ###

from collections import Counter
n=int(input())
balls=[]
distance=[]
if n==1:
  print(1)
else:
  for i in range(n):
    balls.append(list(map(int,input().split())))
    balls.sort(key=lambda x:x[0]+x[1])
  for i in range(n-1):
    for j in range(i+1,n):
      distance.append(str(balls[i][0]-balls[j][0])+","+str(balls[i][1]-balls[j][1]))
  d=Counter(distance)
  print(n-d.most_common()[0][1])
line = input().split()
if line[0] = "H" and line[1] = "H":
    print("H")
elif line[0] = "H" and line[1] = "D":
    print("D")
elif line[0] = "D" and line[1] = "H":
    print("D")
else:
    print("H")
    

### FIXED CODE ###

line = input().split()
if line[0] == "H" and line[1] == "H":
    print("H")
elif line[0] == "H" and line[1] == "D":
    print("D")
elif line[0] == "D" and line[1] == "H":
    print("D")
else:
    print("H")
const = 10 ** 9 + 7
N = int(input())
TABLE = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]T = []
ans = 1
for x in TABLE:
    L = []
    for i in range(1,N + 1):
        count = 0
        while i % x == 0:
            i /= x
            count += 1
        L.append(count)
    T.append(sum(L)+1)
#print(T)
for x in T:
    ans *= x
print(ans % const)

### FIXED CODE ###

const = 10 ** 9 + 7
N = int(input())
TABLE = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]
T = []
ans = 1
for x in TABLE:
    L = []
    for i in range(1,N + 1):
        count = 0
        while i % x == 0:
            i /= x
            count += 1
        L.append(count)
    T.append(sum(L)+1)
#print(T)
for x in T:
    ans *= x
print(ans % const)
N = int(input())
if N >= 195:
  print("3")
elif N >= 165:
  print("2")
elif N >= 105:
  print("1")
else:
  print("0")

### FIXED CODE ###

A,B = map(int, input().split())
print((A-1)*(B-1))
a,b=map(input().split())
print('error'if a+b>=10 else a+b)

### FIXED CODE ###

a,b=map(int,input().split())
print('error'if a+b>=10 else a+b)
ma = lambda:map(int,input().split())
n,k = ma()
ab = []
for i in range(n):
    ab.append((list(ma)))
ab.sort()
c  = 0
for a,b in ab:
    c+=b
    if c>=k:print(a) 


### FIXED CODE ###

ma = lambda:map(int,input().split())
n,k = ma()
ab = []
for i in range(n):
    ab.append((list(ma())))
ab.sort()
c  = 0
for a,b in ab:
    c+=b
    if c>=k:
        print(a)
        break
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    W,H,x,y=map(int,input().split())
    S=W*H/2
    b=1 if x==W//2 and y==H//2 else 0
    print(f'{S} {b}'.format(S=S, b=b))

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    W,H,x,y=map(int,input().split())
    S=W*H/2
    b=1 if x==W/2 and y==H/2 else 0
    print(str(S)+' '+str(b))

if __name__ == '__main__':
    main()
n = input()
xs = input().split(" ")

l = list()
for x in xs:
	l.append(int(x))


ll = list()
for index, argv in enumerate(l):
	for x in range(max(l)):
		ls = list()		
		ab = abs(argv - (n + index))
		ls.append(ab)
	ll.append(ls)

sum_list = list()
for line in ls:
	s = sum(line)
	sum_list.append(s)

print(min(sum_list))


### FIXED CODE ###

input()
a = list(map(int, input().split()))
b = sorted([a[i]-i-1 for i in range(len(a))])
med=b[len(b)//2]
print(sum(list(map(abs,list(map(lambda x: x-med ,b))))))
if α.isupper() == True:
    print("A")
else:
    print("a")

### FIXED CODE ###

n = input()
if n.isupper() == True:
    print("A")
else:
    print("a")
a,b=map(int,input().split())
ans=0
if max(a,b)==a:
  ans=ans+a
  a=a-1
  if max(a,b)==a:
    ans=ans+a
    a=a-1
  elif max(a,b)==b:
    ans=ans+b
    b=b-1
elif max(a,b)==b:
    ans=ans+b
    b=b-1
  if max(a,b)==a:
    ans=ans+a
    a=a-1    
  elif max(a,b)==b:
    ans=ans+b
    b=b-1      
print(ans)   
    

### FIXED CODE ###

a,b=map(int,input().split())
ans=0
if max(a,b)==a:
  ans=ans+a
  a=a-1
  if max(a,b)==a:
    ans=ans+a
    a=a-1
  elif max(a,b)==b:
    ans=ans+b
    b=b-1
elif max(a,b)==b:
  ans=ans+b
  b=b-1
  if max(a,b)==a:
    ans=ans+a
    a=a-1    
  elif max(a,b)==b:
    ans=ans+b
    b=b-1      
print(ans)
import math
def dis(x1,y1,r1,x2,y2,r2):
    if math.sqrt(abs(x1-x2)**2+abs(y1-y2)**2)>r1+r2:
        return  math.sqrt(abs(x1-x2)**2+abs(y1-y2)**2)-r1-r2
    else:
        return 0
import heapq

def dijkstra(s,g,c,n):
    d=[float('inf')]*n
    d[s]=0
    pq=[]
    heapq.heappush(pq,[0,s])
    while len(pq)!=0:
        t,u=heapq.heappop(pq)
        if d[u]<t:
            continue
        for v in g[u]:
            if d[u]+c[u][v]<d[v]:
                d[v]=d[u]+c[u][v]
                heapq.heappush(pq,[d[v],v])
    return d
def main():
    xs,ys,xt,yt=map(int,raw_input().split())
    n=int(raw_input())
    c=[[xs,ys,0]]+[map(int,raw_input().split()) for _ in xrange(n)]+[[xt,yt,0]]
    g=[[] for _ in xrange(n+2)]
    dist=[[float("inf")]*(n+2) for _ in xrange(n+2)]
    for i in xrange(n+2):
        for j in xrange(n+2):
            if i==j:continue
            g[i].append(j)
            dist[i][j]=min(dist[i][j],dis(c[i][0],c[i][1],c[i][2],c[j][0],c[j][1],c[j][2]))
    ans=dijkstra(0,g,dist,n+2)
    print(ans[n+1])
main()

### FIXED CODE ###

n,x=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=0
if a[0]+a[1]>x:
    ans+=a[0]+a[1]-x
    a[1]=max(a[1]-ans,0)
for i in xrange(1,n-1):
    if a[i]+a[i+1]>x:
        ans+=a[i]+a[i+1]-x
        tmp=a[i]+a[i+1]-x
        a[i+1]=max(a[i+1]-tmp,0)

print(ans)
from collections import deque
A=deque(input())
B=deque(input())
C=deque(input())
t="a"
for i in range(len(A+B+C)):
    if t=="a":
        if len(A)==0:
            print("A")
            exit()
        t=A.popleft()   
    if t=="b":
        if len(B)==0:
            print("B")
            exit()
        t=B.popleft()   
    if t=="c":
        if len(C)==0:
            print("C")
            exit()
        t=C.popleft() 

### FIXED CODE ###

from collections import deque
A=deque(input())
B=deque(input())
C=deque(input())
t="a"
for i in range(300):
    if t=="a":
        if len(A)==0:
            print("A")
            exit()
        t=A.popleft()   
    if t=="b":
        if len(B)==0:
            print("B")
            exit()
        t=B.popleft()   
    if t=="c":
        if len(C)==0:
            print("C")
            exit()
        t=C.popleft()
s=input()
print(s.count('+')-s.sount('-'))

### FIXED CODE ###

s=input()
print(s.count('+')-s.count('-'))
from collections import defaultdict

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]

d = defaultdict(list)
class Tree:
    def __init__(self, v):
        self.v = v
        self.neighbors = []

    def set_rank(self,rank,parent):
        self.rank = rank
        for neighbor in self.neighbors:
            if neighbor == parent:
                continue
            neighbor.set_rank(rank=rank+1,parent=self)



trees = {i:Tree(i) for i in range(1,N+1)}

for a,b in AB:
    trees[a].neighbors.append(trees[b])
    trees[b].neighbors.append(trees[a])
trees[1].set_rank(1,None)

group0 = [node.v for node in  trees.values() if node.rank %2 ==0]
group1 = [node.v for node in  trees.values() if node.rank %2]
x = [set(),set(),set()]
for i in range(1,N+1):
    x[i%3].add(i)
if len(group1) < len(group0):
    group1,group0 = group0,group1

result = {}
if len(group0) <= len(x[0]):
    while group0:
        result[group0.pop()]= x[0].pop()
    y = x[0]|x[1]|x[2]
    while group1:
        result[group1.pop()] = y.pop()
else:
    while x[1] and group0:
        result[group0.pop()] = x[1].pop()
    while x[2] and group1:
        result[group1.pop()] = x[2].pop()
    while group0:
        result[group0.pop()] = x[0].pop()
    while group1:
        result[group1.pop()] = x[0].pop()

print(' '.join(str(result[i]) for i in range(1,N+1)))



### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]


class Tree:
    def __init__(self, v):
        self.v = v
        self.neighbors = []

    def set_rank(self, rank, parent):
        self.rank = rank
        for neighbor in self.neighbors:
            if neighbor is parent:
                continue
            neighbor.set_rank(rank=rank + 1, parent=self)


trees = {i: Tree(i) for i in range(1, N + 1)}

for a, b in AB:
    trees[a].neighbors.append(trees[b])
    trees[b].neighbors.append(trees[a])
try:
    trees[1].set_rank(1, None)
except:
    print(-1)
    exit()

group0 = [node.v for node in trees.values() if node.rank % 2 == 0]
group1 = [node.v for node in trees.values() if node.rank % 2]
x = [set(), set(), set()]
for i in range(1, N + 1):
    x[i % 3].add(i)
if len(group1) < len(group0):
    group1, group0 = group0, group1
result = {}
if len(group0) <= len(x[0]):
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    y = x[0] | x[1] | x[2]
    while group1 and y:
        result[group1.pop()] = y.pop()
else:
    while x[2] and group0:
        result[group0.pop()] = x[2].pop()
    while x[1] and group1:
        result[group1.pop()] = x[1].pop()
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    while group1 and x[0]:
        result[group1.pop()] = x[0].pop()
    if group0 or group1:
        print(-1)
        exit()

print(' '.join(str(result[i]) for i in range(1, N + 1)))
import sys
import sympy
import math

input = sys.stdin.readline

n = int(input())
ans = 0

for a in range(1,n+1):
    ans += (n-1) // a
    
print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline

n = int(input())
ans = 0

for a in range(1,n+1):
    ans += (n-1) // a
    
print(ans)
total_subjects, max_points, target_points = map(int, input().split())
subject_points = list(map(int, input().split()))

calc_result = total_subjects * target_points - sum(subject_points)

if calc_result > max_points:
    print(-1)
elif calc_result < 0:
    print(0)
else:
    print(calc_result)

### FIXED CODE ###

small_alpha = str(input())
alpha_list = [chr(ord('a') + i) for i in range(26)]
for num, alpha in enumerate(alpha_list):
    if alpha == small_alpha:
        print(alpha_list[num + 1])
x=raw_input()
print x**3

### FIXED CODE ###

x=eval(input())
print(x**3)
x,y = map(int, input().split())
if x==2 or y==2:
  print("No")
  exit()

if x==4 or x==6 or x==9 or x==11:
  if y==4 or y==6 or y==9 or y~=11:
    print("Yes")
  else:
    print("No")
else:
    print("No")
 

### FIXED CODE ###

x,y = map(int, input().split())
if x==2 or y==2:
  print("No")
  exit()

if x==4 or x==6 or x==9 or x==11:
  if y==4 or y==6 or y==9 or y==11:
    print("Yes")
  else:
    print("No")
else:
    print("Yes")
A=int(input())
B,C=map(int,input().solit())

if A+B>=C:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

A,B,C=map(int,input().split())

if A+B>=C:
  print('Yes')
else:
  print('No')
import sys
def soin(n):
    I=n
    s=0
    R=int(I)
    L=[]
    while s==0:
        for i in range(2,R+1):
            if I%i==0:
                I=I/i
                if I==1:
                    s=1
                L.append(i)
                break
    if len(L)==1:
        print(R)
    else:
        print(L)

n,p= map(int,input().split())
if n==1:
    print(p)
    sys.exit()
l=soin(p)
if len(l)<n:
    print(1)
    sys.exit()
print(min(l))



### FIXED CODE ###

n,p= map(int,input().split())
for i in range(round(p**(1/n)),0,-1):
    if p%(i**n)==0:
        print(i)
        exit()
#C - Day dream
S = input()
S = S[::-1]
end = 1
while end:
    if S.startswith('maerd'):
        S = S.replace('maerd', '', 1)
    elif S.startswith('remaerd'):
        S = S.reaplace('remaerd','',1)
    elif S.startswith('esare'):
        S = S.replace('esare','',1)
    elif S.startswith('resare'):
        S = S.replace('resare', '', 1)
    else:
        end = 0
if len(S) == 0:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

#C - Day dream
S_input = input()
S = S_input
for i in range(len(S_input)):
    S = S[:i]+S_input[len(S_input)-1-i]+S[i+1:]
#print(S)
#S_input = input()
    
#S = S_input[::-1]
end_flg = 1
while end_flg:
    if S.startswith('maerd'):
        S = S.replace('maerd', '', 1)
    elif S.startswith('remaerd'):
        S = S.replace('remaerd','',1)
    elif S.startswith('esare'):
        S = S.replace('esare','',1)
    elif S.startswith('resare'):
        S = S.replace('resare', '', 1)
    else:
        end_flg = 0
if len(S) == 0:
    print('YES')
else:
    print('NO')
N=int(input())
S=list(map(int,input().split()))
bucket=[]
for i in range(N):
    if S[i]=='P':
        bucket[0]+=1
    elif S[i]=='W':
        bucket[1]+=1
    elif S[i]=='G':
        bucket[2]+=1
    else:
        bucket[3]+=1
if 4 - bucket.count(0)==3:
    print('Three')
else:
    print('Four')

### FIXED CODE ###

N=int(input())
S=list(map(str,input().split()))
bucket=[0*i for i in range(4)]
for i in range(N):
    if S[i]=='P':
        bucket[0]+=1
    elif S[i]=='W':
        bucket[1]+=1
    elif S[i]=='G':
        bucket[2]+=1
    else:
        bucket[3]+=1
if 4 - bucket.count(0)==3:
    print('Three')
else:
    print('Four')
def main():
    a, b = map(int, input().split())
    diff = abs(max(b, a) - min(a, b))
    if diff % 2 != 0:
        print("IMPOSSIBLE")
    else:
        bigger = max(a, b)
        ans = bigger - (diff//2)
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    ps = list(map(int, input().split()))
    ps_sort = sorted(ps)

    Count = 0
    for i, j in zip(ps, ps_sort):
        if i != j:
            Count += 1

    if Count == 2 or Count == 0:
        print('YES')
    else:
        print('NO')


if __name__ == "__main__":
    main()
a = []
while True:
    n = input()
    if (n == 0):
        break
    a.append(n)

for i in range(len(a)):
        print('Case '+str(i)+': '+str(a[i]))

### FIXED CODE ###

i=1
while(1):
    n=input()
    if(int(n)==0):
        break
    else:
        print('Case '+str(i)+': '+n)
        i+=1
n = input()
a = int(input())
b = int(input())

if n == "1":
    print("Hello World")
elif n == "2":
    print(a + b)

### FIXED CODE ###

n = input()

if n == "1":
  print("Hello World")
  
elif n == "2":
  a = int(input())
  b = int(input())
  print(a + b)
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k,c = map(int,input().split())
s = input()
dp1 = [0] * (n+1)
dp2 = [0] * (n+1)
# dp[i] = (選択したなかで一番左側のindex,選択した個数)
now = 10 ** 7;count = 0
for i in range(n-1,-1,-1):
  if s[i] == "o" and i + c < now:
    count += 1; now = i
    dp1[i] = (i,count)
  elif i == n-1:dp1[i] = (inf,0)
  else:
    dp1[i] = dp1[i+1]

now = - 10 ** 7;count = 0
for i in range(n):
  if s[i] == "o" and now + c < i:
    count += 1; now = i
    dp2[i] = (i,count)
  elif i == 0:dp2[i] = (-inf,0)
  else:
    dp2[i] = dp2[i-1]

# dp1:右から　　dp2:左から
if dp1[1][1] < k:print(1)
for i in range(1,n-1):
  index0,count0 = dp1[i+1]
  if index0 - c >= 0:
    count0 += dp2[min(index0-c,i-1)][1]
  if count0 < k:
    print(i+1)
if dp2[n-2][1] < k:print(n)
# print(dp2)


### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

if n == 1:
  print(1)
  exit()

dp1 = [0] * (n+1)
dp2 = [0] * (n+1)
# dp[i] = (選択したなかで一番左側のindex,選択した個数)
now = 10 ** 7;count = 0
for i in range(n-1,-1,-1):
  if s[i] == "o" and i + c < now:
    count += 1; now = i
    dp1[i] = (i,count)
  elif i == n-1:dp1[i] = (inf,0)
  else:
    dp1[i] = dp1[i+1]

now = - 10 ** 7;count = 0
for i in range(n):
  if s[i] == "o" and now + c < i:
    count += 1; now = i
    dp2[i] = (i,count)
  elif i == 0:dp2[i] = (-inf,0)
  else:
    dp2[i] = dp2[i-1]

# dp1:右から　　dp2:左から
if dp1[1][1] < k:print(1)
for i in range(1,n-1):
  index0,count0 = dp1[i+1]
  if index0 - c >= 0:
    count0 += dp2[min(index0-c,i-1)][1]
  if count0 < k:
    print(i+1)
if dp2[n-2][1] < k:print(n)
# print(dp2)
n = input()
k = int(input())

n_list = []
for a in n:
    n_list.append(int(a))
n_num = len(n_list)

dp = [[[0] * (n_num + 1) for _ in range(2)]for _ in range(n_num + 1)]

dp[0][0][0] = 1
for i in range(n_num):
    for smaller in range(2):
        for j in range(n_num):
            lim = 9 if smaller else n_list[i]
            for x in range(lim + 1):
                if x != 0:
                    ns = j + 1
                else:
                    ns = j
                nlt = smaller | (x < n_list[i])
                dp[i + 1][nlt][ns] += dp[i][smaller][j]
ans = dp[n_num][0][k] + dp[n_num][1][k]
print(ans)

### FIXED CODE ###

n = input()
k = int(input())

n_list = []
for a in n:
    n_list.append(int(a))
n_num = len(n_list)

if n_num < k:
    print('0')
else:

    dp = [[[0] * (n_num + 1) for _ in range(2)]for _ in range(n_num + 1)]

    dp[0][0][0] = 1
    for i in range(n_num):
        for smaller in range(2):
            for j in range(n_num):
                lim = 9 if smaller else n_list[i]
                for x in range(lim + 1):
                    if x != 0:
                        ns = j + 1
                    else:
                        ns = j
                    nlt = smaller | (x < n_list[i])
                    dp[i + 1][nlt][ns] += dp[i][smaller][j]
    ans = dp[n_num][0][k] + dp[n_num][1][k]
    print(ans)
N = int(input())
sum = int(N % 10) + (int(N/10))
if sum % 9 != 0:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

N = int(input())
x = N //1000
x1 = (N - x*1000)//100
x2 = (N - x*1000 - x1*100)//10
x3 = N - x*1000 - x1*100 - x2*10
sum = x+x1+x2+x3
if sum % 9 != 0:
    print("No")
else:
    print("Yes")
w,h,x,y = [int(x) for x in input().split()]

if w % x == 0 and h % y == 0:
    print((w*h)/2, 1)
else:
    print((w*h)/2, 0)

### FIXED CODE ###

X, H, x, y = [int(x) for x in input().split()]

if 2 * x == X and 2 * y == H:
    print((X * H) / 2, 1)
else:
    print((X * H) / 2, 0)
x=map(int,input().split())
h=x//500 * 1000
x%=500
h+=x//5
print(h)

### FIXED CODE ###

x=int(input())
h=(x//500)*1000
x%=500
h+=(x//5)*5
print(h)
# coding: utf-8
from functools import lru_cache


def solve(*args: str) -> str:
    n = int(args[0])
    LR = []
    for a in args[1:]:
        LR.append(tuple(map(int, a.split())))

    dp = DP(LR)

    return str(dp.search_max(0, 0, 10**9, 0, 10**9))


class DP:
    def __init__(self, LR: list):
        self.LR = LR

    @lru_cache(maxsize=None)
    def search_max(self, index: int, l1: int, r1: int, l2: int, r2: int)\
            -> int:
        ret = 0

        if index < len(self.LR):
            l, r = self.LR[index]
            ret = max(
                self.search_max(index+1, max(l, l1), min(r, r1), l2, r2),
                self.search_max(index+1, l1, r1, max(l, l2), min(r, r2))
            )
        else:
            if l1 == 0 or l2 == 0:
                ret = 0
            else:
                ret = max(0, (r1-l1)) + max(0, (r2-l2) + 2)
        # print((l1, r1, l2, r2))
        return ret


if __name__ == "__main__":
    n = input()
    print(solve(*([n]+[input() for _ in range(int(n))])))


### FIXED CODE ###

# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    LR = [tuple(map(int, a.split())) for a in args[1:]]
    L, R = zip(*LR)

    ret = 0

    p, q = np.argmax(L), np.argmin(R)
    lp, rq = L[p], R[q]

    ret = max(0, 1+rq-lp) + max(0, max(1+r-l for l, r in LR))

    AB = [[max(0, 1+r-lp), max(0, 1+rq-l)] for l, r in LR]
    AB.sort(key=lambda x: (x[0], -x[1]))
    A, B = map(list, zip(*AB))

    # for i in range(1, n):
    #     ret = max(ret, min(A[i:]) + min(B[:i]))
    b_min = 1+10**9
    for i in range(n-1):
        b_min = min(b_min, B[i])
        ret = max(ret, b_min + A[i+1])

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))