Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n=n_in()

base=[]

for _ in range(n):
    s = s_in()

    c = s[0]
    cnt = 1
    ar = []
    for t in range(1,len(s)):
        if s[t-1] == s[t]:
            cnt += 1
        else:
            ar.append((c,cnt))
            c = s[t]
            cnt = 1
    ar.append((c,cnt))

    start = 0
    if ar[0][0] == ")":
        start = 1

    r = 0 # ( の数
    sgn = 1
    for c,cnt in ar[start:]:
        r += sgn*cnt
        sgn *= -1


    res = ()
    if ar[0][0] == ")":
        if r >= 0:
            res = (ar[0][1], r)
        else:
            res = (ar[0][1]-r,0)
    else:
        if r >= 0:
            res = (0, r)
        else:
            res = (r, 0)

    base.append(res)

i_cnt = 0
j_cnt = 0

base2 = []

for i,j in base:
    i_cnt += i
    j_cnt += j

    if j > 0:
        base2.append((i,-(j-i),j))

if i_cnt != j_cnt:
    print("No")
    exit()

base2.sort()

current = 0


for i,p,j in sorted(filter(lambda x: x[1] <= 0 ,base2)):
    if current < i:
        print("No")
        exit()
    current -= i
    current += j

base3 = []
for i,p,j in filter(lambda x: x[1] > 0 ,base2):
    base3.append((p,i,j))

base3.sort()

if len(base3) > 0:
    1/0

for p,i,j in base3:
    if current < i:
        print("No")
        exit()
    current -= i
    current += j
    
print("Yes")
        


### FIXED CODE ###


import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n=n_in()

base=[]

for _ in range(n):
    s = s_in()

    c = s[0]
    cnt = 1
    ar = []
    for t in range(1,len(s)):
        if s[t-1] == s[t]:
            cnt += 1
        else:
            ar.append((c,cnt))
            c = s[t]
            cnt = 1
    ar.append((c,cnt))

    start = 0
    if ar[0][0] == ")":
        start = 1

    r = 0 # ( の数
    sgn = 1
    for c,cnt in ar[start:]:
        r += sgn*cnt
        sgn *= -1


    res = ()
    if ar[0][0] == ")":
        if r >= 0:
            res = (ar[0][1], r)
        else:
            res = (ar[0][1]-r,0)
    else:
        if r >= 0:
            res = (0, r)
        else:
            res = (-r, 0)

    base.append(res)

i_cnt = 0
j_cnt = 0

base2 = []

for i,j in base:
    i_cnt += i
    j_cnt += j

    if j > 0:
        base2.append((i,-(j-i),j))

if i_cnt != j_cnt:
    print("No")
    exit()

base2.sort()

current = 0


for i,p,j in sorted(filter(lambda x: x[1] <= 0 ,base2)):
    if current < i:
        print("No")
        exit()
    current -= i
    current += j

base3 = []
for i,p,j in filter(lambda x: x[1] > 0 ,base2):
    base3.append((p,i,j))

base3.sort()

for p,i,j in base3:
    if current < i:
        print("No")
        exit()
    current -= i
    current += j
    
print("Yes")
def f(n):
    if n < 2:
        return 1
    return n * f(n-2)

n = int(input())
F_s = str(f(n))
ans = 0

for i in range(0, len(F_s))[::-1]:
    if int(F_s[i]) == 0:
       ans += 1
    else:
         break
     
print(ans)

### FIXED CODE ###

N = int(input())
count = 0

if N % 2 != 0:
    print(0)
    exit()
P = 1
k = 2 * 5

while k <= N:  
    count += N//k
    k *= 5
    
print(count)
s = input()
ans = 0
for i in range(len(s)):
  for j in range(len(s)):
  a = s[i:i+j]
  if int(a) % 2019 == 0:
    ans += 1

print(ans)

### FIXED CODE ###

s,l = (input(),2019)
m,a,r = ([1]+[0]*l,0,0)
for i,e in enumerate(s[::-1]):
    a += int(e)*pow(10,i,l)
    r += m[a%l]
    m[a%l] += 1
print(r)
n = int(input())

if n%2 == 0:
    print(n/2)
else:
    print(math.floor(n/2)+1)

### FIXED CODE ###

import math

n = int(input())

if n%2 == 0:
    print(n//2)
else:
    print(math.floor(n//2)+1)
n,k=map(int,input().split())
s=[0,0,0]

for i in range(k):
  d=int(input())
 
  List=list(map(int,input().split()))
  for i in range(d):
    s[List[i]-1]=1
print(n-sum(s))

### FIXED CODE ###

n,k=map(int,input().split())
s=[]
for i in range(n):
  s.append(0)


for i in range(k):
  d=int(input())
 
  List=list(map(int,input().split()))
  for i in range(d):
    s[List[i]-1]=1
print(n-sum(s))
anum,bnum,acc = map(int,input().split())
alist = list(map(int,input().split()))
blist = list(map(int,input().split()))

asum = 0;bsum = 0
ans = 0;a = 0;b = 0
while asum + alist[a] <= acc:
    asum += alist[a];a+=1
    if a == anum:
        break

while asum + blist[b] <= acc:
    bsum += blist[b];b += 1
    if b == bnum:
        break

if a == 0 and b == 0:
    pass
elif (a == anum and b == bnum) or a == 0:
    ans = a + b
else:
    ans = a + b
    for i in range(a):
        while asum - alist[a-(i+1)] + bsum + blist[b] <= acc:
            bsum += blist[b];b += 1
            if a + b > ans:
                ans = a + b
            if b == bnum:
                break

print(ans)


### FIXED CODE ###

anum,bnum,acc = map(int,input().split())
alist = list(map(int,input().split()))
blist = list(map(int,input().split()))

asum = [0]
bsum = [0]
ans = 0
for i in range(anum):
    asum.append(asum[i]+alist[i])
for i in range(bnum):
    bsum.append(bsum[i]+blist[i])

b = bnum
for a in range(anum+1):
    if asum[a] > acc:
        break
    while asum[a] + bsum[b] > acc:
        b -=1
    ans = max(ans,a+b)

print(ans)
import math
n = int(input())
a = list(map(int, input().split()))

n2 = math.ceil(n/2)
cnt = 0
ans = 0
seq = []
for i in reversed(range(n2)):
    sumi = sum([a[j] for j in range(i,n,i+1)])
    if sumi%2 != a[i-1]:
        a[i*n//i-1] += 1
        seq.append(i*n//i)
        if a[i*n//i-1] > 1:
            ans = -1
            break
        else:
            cnt += 1
    
if ans == -1:
    print(-1)
else:
    print(cnt)
    print(' '.join(list(map(str, seq))))

### FIXED CODE ###


n = int(input())
a = list(map(int, input().split()))
b = [0]*n
cnt = 0
ans = 0
seq = []
for i in reversed(range(1,n+1)):
    sumi = sum(b[i-1:n:i])
    if sumi % 2 == a[i-1]:
        continue
    else:
        b[i-1] = 1
        seq.append(i)
        cnt += 1
    
if ans == -1:
    print(-1)
else:
    print(cnt)
    print(' '.join(list(map(str, seq))))
a = int(input())
b = input()
x = 0

if (a==0) :
	print('DENIED')
elif (b.count(0) > 0):
	print('DENIED')
else:
  for i in b:
      if i % a == 0:
          x += 1
  if x == len(b):
      print('APPROVED')
  else:
      print('DENIED')

### FIXED CODE ###

a = int(input())
 
b=list(map(int, input().split())) 
x = 0
c = 0
    
for i in b:
  if ((i % 3 == 0) or (i % 5 == 0)) and (i % 2 == 0):
    x += 1

for t in b:
  if (t%2==0):
    c += 1;

if x == c:
  print('APPROVED')
else :
  print('DENIED')
A = list(map(int, input().split()))
println((A[0]*A[1])//2)

### FIXED CODE ###

A = list(map(int, input().split()))
print((A[0]*A[1])//2)
n = int(input())
t, a = list(map(int, input().split(' ')))
hs = list(map(int, input().split(' ')))

diff_a = list(map(lambda h: int(abs(a - t + h * 0.006)), hs))
print(diff_a)
ans = 100_000
result = -1
for i in range(n):
    if diff_a[i] <= ans:
        result = i + 1
        ans = diff_a[i]

print(result)


### FIXED CODE ###

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

def get_dif(h):
    temp = t - h * 0.006
    dif = abs(temp - a)
    return dif

result = hn.index(min(hn, key=get_dif)) + 1
print(result)
a=[*input()]
b=a[::-1]
n=len(a)
if n==1:
    print(0)
else:
    x=0
    y=0
    for i in range(n-1):
        if a[i]==a[i+1]:
            x+=1
            if a[i]=='0':
                a[i+1]='1'
            else:
                a[i+1]='0'
        if b[i]==b[i+1]:
            y+=1
            if b[i]=='0':
                b[i+1]='1'
            else:
                b[i+1]='0'
    print(min(x,y))

### FIXED CODE ###

a=list(input())
b=a[::-1]
n=len(a)
if n==1:
    print(0)
else:
    x=0
    y=0
    for i in range(n-1):
        if a[i]==a[i+1]:
            x+=1
            if a[i]=='0':
                a[i+1]='1'
            else:
                a[i+1]='0'
        if b[i]==b[i+1]:
            y+=1
            if b[i]=='0':
                b[i+1]='1'
            else:
                b[i+1]='0'
    print(min(x,y))
s=input()
for i in range(len(s)):
    if s[i]=="A":
        a=i
for i in range(a+1,len(s)):
    if s[i]=="Z":
        z=i
print(z-a+1)

### FIXED CODE ###

s=input()
for i in range(len(s)):
    if s[i]=="A":
        a=i
        break
for i in range(len(s)-1,0,-1):
    if s[i]=="Z":
        z=i
        break
print(z-a+1)
N = int(input())
X = input()

def popcount(x):
    tmp = x
    count = 0
    while tmp > 0:
        if tmp & 1 == 1:
            count += 1
        tmp >>= 1
    
    return count

tmp_pop_X = X.count('1')

for i in range(N):
    if X[i] == '0':
        X_next = int(X,2) + 2**(N-1-i)
        X_pop_next = tmp_pop_X + 1
    else:
        X_next = int(X,2) - 2**(N-1-i)
        X_pop_next = tmp_pop_X - 1
        
    X_next = X_next % X_pop_next
    ans = 1
    
    while X_next != 0:
        X_next = X_next % popcount(X_next)
        ans += 1
        
    print(ans)

### FIXED CODE ###

n = int(input())
s = input()
x = int(s, 2)
pcx = s.count("1")
pc1 = x % (pcx - 1) if pcx > 1 else 0
pc2 = x % (pcx + 1)

def f(j):
    cnt = 0
    while j:
        j %= bin(j).count("1")
        cnt += 1
    return cnt

for i, y in enumerate(s):
    k = n - 1 - i
    if y == "0":
        print(f((pc2 + pow(2, k, pcx + 1)) % (pcx + 1)) + 1)
    elif pcx > 1:
        print(f((pc1 - pow(2, k, pcx - 1)) % (pcx - 1)) + 1)
    else:
        print(0)
s = [0] * 13
h = [0] * 13
c = [0] * 13
d = [0] * 13

num = int(input())
for i in range(num):
    m, n = input().split()
    x = int(n)
    if m == "S":
        s[x] = 1
    if m == "H":
        h[x] = 1
    if m == "C":
        c[x] = 1
    if m == "D":
        d[x] = 1

for i in range(1,13):
    if s[i] == 0:
        print("S %d" % i)

for i in range(1,13):
    if h[i] == 0:
        print("H %d" % i)

for i in range(1,13):
    if c[i] == 0:
        print("C %d" % i)

for i in range(1,13):
    if d[i] == 0:
        print("D %d" % i)






### FIXED CODE ###

#
# 6b
#

def main():
    n = int(input())
    c = []
    for i in range(n):
        m, r = input().split()
        r = int(r)
        c.append([m, r])
    for M in ["S", "H", "C", "D"]:
        for R in range(1, 14):
            for i in range(n):
                if c[i] == [M, R]:
                    break
            else:
                print(*[M, R])


if __name__ == '__main__':
    main()
import sys
def dfs(v, tm):
    dts[v] = est[v] = tm + 1
    child = 0

    for i in adj[v]:
        if est[i] == float('inf'):
            child += 1
            parents[i] = v
            dfs(i, tm + 1)
            est[v] = min(est[v], est[i])

            if parents[v] is None and child > 1: aps[v] = True
            if parents[v] is not None and est[i] >= dts[v]: aps[v] = True

        elif parents[v] != i:
            est[v] = min(est[v], dts[i])


nv, ne = map(int, input().split(' '))
adj = [[] for _ in range(nv)]
est = [float('inf')] * nv
parents = [None] * nv
aps = [False] * nv
dts = [0] * nv

for _ in range(ne):
    s, t = map(int, input().split(' '))
    adj[s].append(t)
    adj[t].append(s)

dfs(0, 0)

for i in range(nv):
    if aps[i]:
        print(i)

### FIXED CODE ###

from sys import stdin
import sys
from math import isinf
INF = float("inf")
sys.setrecursionlimit(100000)
def dfs(v, tm):
    dts[v] = est[v] = tm + 1
    child = 0
    for i in adj[v]:
        if est[i] == float('inf'):
            child += 1
            parents[i] = v
            dfs(i, tm + 1)
            est[v] = min(est[v], est[i])
            if parents[v] is None and child > 1: aps[v] = True
            if parents[v] is not None and est[i] >= dts[v]: aps[v] = True
        elif parents[v] != i:
            est[v] = min(est[v], dts[i])
n, m = map(int, stdin.readline().split())
adj = [[] for _ in range(n)]
est = [float('inf')] * n
parents = [None] * n
aps = [False] * n
dts = [0] * n
for _ in range(m):
    s, t = map(int, stdin.readline().split())
    adj[s].append(t)
    adj[t].append(s)
dfs(0, 0)
for i in range(n):
    if aps[i]:
        print(i)
s_odd=list(A=input())[0::2]
s_even=list(A)[1::2]
if s_odd.find('L')==-1 and s_even.find('R')==-1:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s=list(input())

s_odd=''.join(s[0::2]) #偶数項、奇数項に分類する
s_even=''.join(s[1::2])

if s_odd.find('L')==-1 and s_even.find('R')==-1:
    print('Yes')
else:
    print('No')
import sys
from collections import deque
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
L = [deque([]) for _ in range(N)]

for m in range(M):
    l, r, d = [int(x) for x in input().strip().split()]
    L[l-1].append((r, d))
    L[r-1].append((l, -d))

D = [0] * N
F = [False] * N

def dfs(n, d):
    if F[n-1]:
        if D[n-1] == d:
            return True
        else:
            return False
    F[n-1] = True
    D[n-1] = d
    for nn, d_ in L[n-1]:
        if not dfs(nn, d+d_):
            return False
    else:
        return True

for n in range(1, N+1):
    if not dfs(n, D[n-1]):
        print('No')
        exit()
else:
    print('Yes')

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
L = [deque([]) for _ in range(N)]

for m in range(M):
    l, r, d = [int(x) for x in input().strip().split()]
    L[l-1].append((r, d))
    L[r-1].append((l, -d))

D = [0] * N
F = [False] * N

def dfs(n, d):
    # print('n = {}, d = {}'.format(n, d))
    if F[n-1]:
        if D[n-1] == d:
            # print('  already passed')
            return True
        else:
            # print('  already passed, but wrong')
            return False
    F[n-1] = True
    D[n-1] = d
    for nn, d_ in L[n-1]:
        # print('  dfs({}, {})'.format(nn, d+d_))
        if not dfs(nn, d+d_):
            return False
    else:
        return True

for n in range(1, N+1):
    if not dfs(n, D[n-1]):
        print('No')
        exit()
else:
    print('Yes')
N = int(input())
A = list(int(i) for i in input().split())
count_m = 0
count_z = 0

for i in A:
  if i < 0:
    count_m += 1
  elif i == 0:
    count_z += 1

A_abs = [abs(i) for i in A]
if count_m%2 == 0 || count_m+count_z%2 == 0:
  print(sum(A_abs))
  
else:
  A_min = A.index(min(A_abs))
  A_abs[A_min] = A[A_min]*(-1)
  print(sum(A_abs))

### FIXED CODE ###

N = int(input())
A = list(int(i) for i in input().split())
count_m = 0
count_z = 0

for i in A:
  if i < 0:
    count_m += 1
  elif i == 0:
    count_z += 1

A_abs = [abs(i) for i in A]
if count_m%2 == 0 or (count_m+count_z)%2 == 0:
  print(sum(A_abs))
  
else:
  A_min = A_abs.index(min(A_abs))
  A_abs[A_min] = A_abs[A_min]*(-1)
  print(sum(A_abs))
def bin_tree( pri , li_pri , len_li ):
    #pri: どこに入れていいかわからない値段
    #li_pri: 値段のリスト(昇順)
    #len_li: リストの長さ
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        guess = li_pri[mid]
        if guess >= pri:
            hi = mid
        else:
            lo = mid
    return lo

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))
A.sort()

print(A)

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2

    ans = bin_tree( pri , A , N - 1 )
    A[ans:ans] = [pri]

    print(A)
    

F_pri = 0
for i in range(N):
    F_pri += A[i]
print(F_pri)

### FIXED CODE ###

def bin_tree( pri , li_pri , len_li ):
    #pri: どこに入れていいかわからない値段
    #li_pri: 値段のリスト(昇順)
    #len_li: リストの長さ
    lo = 0
    hi = len_li - 1
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        guess = li_pri[mid]
        if guess >= pri:
            hi = mid
        else:
            lo = mid
    return lo

I = input().split()
N = int(I[0])
M = int(I[1])
# N: 品物の数
# M: 割引券の数
# A: 品物の値段行列
A = list(map(int , input().split()))
A.sort()

while M > 0:
    M -= 1
    pri = A.pop( N - 1 )
    pri = pri // 2
    if len(A) == 0:
        ans = 0
    elif (pri < A[0] ):
        ans = 0
    else:
        ans = bin_tree( pri , A , N - 1 ) + 1
    # ans: pri以上となる値段のうち最小のインデックス
    A[ans:ans] = [pri]    

F_pri = 0
for i in range(N):
    F_pri += A[i]
print(F_pri)
n = int(input())
ll = [int(w) for w in input().split()]
ll.sort(reverse=True)

ans = 0
for ei, i in enumerate(ll):
    for ej, j in enumerate(ll[ei + 1:]):
        ans += len([w for w in ll[ei + ej + 2] if w > i - j])

print(ans)


### FIXED CODE ###

import bisect

n = int(input())
ll = [int(w) for w in input().split()]
ll.sort()

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans += bisect.bisect_left(ll, ll[i] + ll[j]) - (j + 1)

print(ans)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N = int(input())
    S = input()

    R = 0
    G = 0
    B = 0

    for s in S:
        if s == 'R':
            R += 1
            continue
        elif s == 'G':
            G += 1
            continue
        elif s == 'B':
            B += 1
    

    total = 0

    for i in range(N):
        for j in range(i+1, N):
            if S[i] != S[j] and S[j] != S[2*j-i] and S[2*j-i] != S[i]:
                total += 1

    print(N - total)


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N = int(input())
    S = input()

    R = 0
    G = 0
    B = 0

    for s in S:
        if s == 'R':
            R += 1
            continue
        elif s == 'G':
            G += 1
            continue
        elif s == 'B':
            B += 1
    

    total = 0

    for i in range(N-2):
        for j in range(i+1, N-1):
            if 2*j-i >= N:
                break
            if S[i] != S[j] and S[j] != S[2*j-i] and S[2*j-i] != S[i]:
                total += 1

    print(R*G*B - total)


if __name__ == '__main__':
    main()
word = string(input())
texts = list(string, input().split())

ans = texts.count(word)

print ans

### FIXED CODE ###

word = input().lower()
texts = []
while True:
  str = input()
  if str == 'END_OF_TEXT':
    break
  texts.extend([s.lower() for s in str.split()] )
    

ans = texts.count(word)

print(ans)
def resolve():
    N = int(input())
    import math
    print(math.ceil(N/2))

if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    S = input()
    print("No" if S in ["AAA", "BBB"] else "Yes")

if '__main__' == __name__:
    resolve()
import bisect

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
rev_A = A[::-1]

num_A_or_more = [0]*(10**5)
for a in A:
  num_A_or_more[a-1] += 1


for i in range(10**5-1, 0, -1):
  num_A_or_more[i-1] += num_A_or_more[i]


def check(x):
  count = 0
  for a in A:
    idx = max(x-a-1, 0)
    count += num_A_or_more[idx]
  
  return count>=M


left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

x = left
if check(right):
  x = right

accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)

ans = 0
count = 0
surplus = 2*10**5
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+A[idx])


print(ans - (count-M)*surplus)

### FIXED CODE ###

import bisect

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
rev_A = A[::-1]

def check(x, a=A, m=M):
  result = False
  n = len(a)
  count = 0
  for ai in a:
    count += (n - bisect.bisect_left(a, x-ai))
  
  return count>=m


left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

x = left
if check(right):
  x = right

accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)

ans = 0
count = 0
surplus = 2*10**5
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+A[idx])


print(ans - (count-M)*surplus)
a, b, c = map(int, input().split())
for i in range(min(a,b), 0, -1):
  if a%i==0 and b%i==0:
    count+=1
  if count==c:
    print(i)
  

### FIXED CODE ###

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

count = 0
for i in range(min(a,b), 0, -1):
  if a%i==0 and b%i==0:
    count+=1
  if count==c:
    print(i)
    break
N, K = map(int, input().split())
tmp = N

a = abs(N - K)
ans = N % a

if ans == 1:
    print(0)
else:
    print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
tmp = N % K
print(min(tmp, abs(tmp - K)))
n = int(input())
min_n = 0
max_n = -2 * 10**9
for i in range(n):
    x = int(input())
    min_n = min(x,min_n)
    max_n = max(max_n,x - min_n)
print max_n

### FIXED CODE ###

n = int(input())
min_n = 2 * 10**9
max_n = -2 * 10**9
for i in range(n):
    x = int(input())
    max_n = max(max_n,x - min_n)
    min_n = min(x,min_n)
print (max_n)
N = int(input())
H = list(map(int,input().split()))
ans = []
temp = 0

for i in range(0,N-1):
    if H[i] >= H[i+1]:
        temp += 1
    else:
        temp = 0
    ans.append(temp)
        
print(max(ans))

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
temp = 0
ans = []

for i in range(N-1):
    if H[i] >= H[i+1]:
        temp += 1
    else:
        ans.append(temp)
        temp = 0
ans.append(temp)

print(max(ans))
import math


def divisor(num):
    if num < 0:
        return 0
    elif num == 1:
        return 1
    else:
        divisor_list = [1, ]
        for i in range(2, int(math.sqrt(num) + 1)):
            if num % i == 0:
                divisor_list.append(i)
        return divisor_list


n = int(input())

divisor_list = divisor(n)
minA = divisor_list[-1]
print(len(str(n//minA)))


### FIXED CODE ###

import math


def divisor(num):
    if num < 0:
        return 0
    elif num == 1:
        return [1, ]
    else:
        divisor_list = [1, ]
        for i in range(2, int(math.sqrt(num) + 1)):
            if num % i == 0:
                divisor_list.append(i)
        return divisor_list


n = int(input())
divisor_list = divisor(n)
minA = divisor_list[-1]
print(len(str(n//minA)))
S = list(input())
USED = [False] * 26

for s in S:
  USED[ord(s)-96] = True
  
ok = False
ans = None
for i in range(26):
  if not USED[i]:
    ans = chr(96+i)
    ok = True
    break
    
if ok:
  print(ans)
else:
  print("None")

### FIXED CODE ###

S = list(input())
USED = [False] * 26

for s in S:
  USED[ord(s)-97] = True
  
ok = False
ans = None
for i in range(26):
  if not USED[i]:
    ans = chr(97+i)
    ok = True
    break
    
if ok:
  print(ans)
else:
  print("None")
a,b,c=map(int, input().split())
print("YES" if b-a=c-b else "NO")

### FIXED CODE ###

a,b,c=map(int, input().split())
print("YES" if b-a==c-b else "NO")
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

# 体力のリスト
sum_hp_list = []

min_x = min(x_list)
max_x = max(x_list)

for i in range(min_x, max_x):
    sum_hp = 0
    for x in x_list:
        sum_hp += (x-i)**2
    sum_hp_list.append(sum_hp)

print(min(sum_hp_list))


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from sys import stdin

n = int(input())
x_list_str = stdin.readline().rstrip().split()
x_list = [int(i) for i in x_list_str]

# 体力のリスト
sum_hp_list = []

min_x = min(x_list)
max_x = max(x_list)

if min_x == max_x:
    print(0)
    exit()

for i in range(min_x, max_x):
    sum_hp = 0
    for x in x_list:
        sum_hp += (x-i)**2
    sum_hp_list.append(sum_hp)

print(min(sum_hp_list))
S = input()
K = int(input())

i = 0
while S[i]=='1':
    i += 1

if i >= K:
    print(1)
else:
    print(S[i])

### FIXED CODE ###

S = input()
K = int(input())

ones = 0
for c in S:
    if c == '1':
        ones += 1
    else:
        n = c
        break

print(1 if ones >= K else n)