Harryxun/stf_run huggingface dataset:
import bisect
def LIS(a):
    lis = [a[0]]
    for i in range(len(a)):
        if i != 0 and a[i] >= lis[-1]:
            lis.append(a[i])
        else:
            index = bisect.bisect_right(lis,a[i])
            lis[index] = a[i]
    return len(lis)

def main():
    n = int(input())
    a = [-int(input()) for _ in range(n)]
    print(LIS(a))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import bisect
from collections import deque
def LIS(a):
    lis = deque()
    lis.append(-1)
    for i in range(len(a)):
        index = bisect.bisect_left(lis,a[i])
        if index == 0:
            lis.appendleft(a[i])
        else:
            lis[index-1] = a[i]
    return len(lis)

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    print(LIS(a))

if __name__ == "__main__":
    main()
text = raw_input()
count = {} #a~zの出現回数を記録

for i in range(26):
    count[(i)] = 0
    
for i in range(len(text)):
    if(ord(text[i]) >= ord('a') and ord(text[i]) <= ord('z')):
        count[(ord(text[i]))-ord('a')] += 1

#出現回数の表示
for i in range(26):
    print '%s : %d' %(unichr(i+ord('a')), count[(i)])

exit(0)

### FIXED CODE ###

count = {}
for i in range(26):
    count[(i)] = 0

while True:
    try:
        x = raw_input()
    except:
        break
    for i in range(len(x)):
        if(ord('a') <= ord(x[i]) and ord(x[i]) <= ord('z')):
            count[(ord(x[i])-ord('a'))] += 1
        elif(ord('A') <= ord(x[i]) and ord(x[i]) <= ord('Z')):
            count[(ord(x[i])-ord('A'))] += 1

for i in range(26):
    print '%s : %d' %(chr(i+ord('a')), count[(i)])
exit(0)
n,m=map(int,input().split())
mod=10**9+7
t=[int(input()) for i in range(m)] 
dp=[-1]*(n+1)

dp[0]=0
dp[1]=1
dp[2]=1

for i in range(m):
    dp[t[i]]=0

for i in range(3,n+1):
    if dp[i]==-1:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%mod)


### FIXED CODE ###

n,m=map(int,input().split())
mod=10**9+7
t=[int(input()) for i in range(m)] 
dp=[-1]*(n+1)

dp[0]=1
dp[1]=1
for i in range(m):
    dp[t[i]]=0


for i in range(2,n+1):
    if dp[i]==-1:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%mod)
from math import factorial

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))
n,k = map(int,input().split())


for i in range(1,k+1):
    ans = (combinations_count(n-k+1,i)*combinations_count(k-1,i-1))
    print(ans%(10**9+7))

### FIXED CODE ###

import math

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

def combinations_count(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))



for i in range(1,k+1):
    if n-k+1>=i:
        ans = (combinations_count(n-k+1,i)%(10**9+7)*combinations_count(k-1,i-1)%(10**9+7))
        print(ans%(10**9+7))
    else:
        print(0)
n = int(input())
h = list(map(int,input().split()))

for i in range(n-1):
    print(h)
    if h[i] < h[i+1]:
        h[i+1] -= 1

    elif h[i] > h[i+1]:
        print('No')
        exit()

print('Yes')

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
h[0] -= 1
for i in range(n-1):
    if h[i] < h[i+1]:
        h[i+1] -= 1

    elif h[i] > h[i+1]:
        print('No')
        exit()

print('Yes')
s=input()
if s[1]=='B':
  s[1]='R'
else:
  s[1]='B'
print(s)

### FIXED CODE ###

s=input()

if s[1]=='B':
  print('ARC')
else:
  print('ABC')
n=int(input())
x=input()
p=x.count('1')

#愚直に解く関数を定義
def solve(n):
    count=0
    while n:
        popcount=bin(n).count('1')
        n%=popcount
        count+=1
    return count+1

#popcount(x)が0,1だった場合に対応
if p==0:
    for i in range(n):
        print(1)
    exit()
elif p==1:
    exit(1)
    z=x.index('1')
    for i in range(n):
        if i==z:
            print(0)
        else:
            tmp=(pow(2,z,p+1)+pow(2,i,p+1))%(p+1)
            print(solve(tmp))
    exit()


#2^i mod(p+1),2^i mod(p-1)のリストを作成
a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))

#x mod(p+1),x mod(p-1)を計算
a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]

#本計算
for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i])%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp))

### FIXED CODE ###

n=int(input())
x=input()
p=x.count('1')

#愚直に解く関数を定義
def solve(n):
    count=0
    while n:
        popcount=bin(n).count('1')
        n%=popcount
        count+=1
    return count+1

#popcount(x)が0,1だった場合に対応
if p==0:
    for i in range(n):
        print(1)
    exit()
elif p==1:
    z=x.index('1')
    t=pow(2,n-z-1,p+1)
    for i in range(n):
        if i==z:
            print(0)
        else:
            tmp=(t+pow(2,n-i-1,p+1))%(p+1)
            print(solve(tmp))
    exit()


#2^i mod(p+1),2^i mod(p-1)のリストを作成
a,b=[],[]
for i in range(n):
    a.append(pow(2,i,p+1))
    b.append(pow(2,i,p-1))

#x mod(p+1),x mod(p-1)を計算
a1,b1=0,0
for i in range(n):
    if x[-1-i]=='1':
        a1+=a[i]
        b1+=b[i]

#本計算
for i in range(n):
    if x[i]=='1':
        tmp=(b1-b[-1-i])%(p-1)
    else:
        tmp=(a1+a[-1-i])%(p+1)
    print(solve(tmp))
N,Q=int(input()).split()
S=input()
l_list=[]
r_list=[]
for i in range(Q):
  l,r=int(input()).split()
  l_list.append(l)
  r_list.append(r)
for i in range(Q):
  S_i=S[l_list[i]-1,r_list[i]]
  n=0
  while "AC" in S_i:
    n+=1
  print(n)

### FIXED CODE ###

N,Q=map(int,(input()).split())
S=input()
l_list=[]
r_list=[]
for i in range(Q):
  l,r=input().split()
  l_list.append(int(l))
  r_list.append(int(r))
count=0
AC_count=[0]
for i in range(1,N+2):
  if S[i-1:i+1]=="AC":
    count+=1
  AC_count.append(count)
AC_count.append(count)
k=0
for j in range(Q):
  k=AC_count[r_list[j]-1]-AC_count[l_list[j]-1]
  print(k)
N,K = map(int,input().split(" "))
array = list(map(int,input().split(" ")))

minus = 0
while array[minus] < 0 and minus < N:
    minus += 1

#first,last = max(minus-K,0),min(minus,N-K)
first = 0
last = N-K
ans = 2*(array[N-1]- array[0])

for i in range(first,last+1):
    m_dist, p_dist = array[i], array[K-1+i]
    if m_dist*p_dist <=0:
        dist_i = min(abs(m_dist),abs(p_dist))*2+max(abs(m_dist),p_dist)
    else:
        dist_i = max(abs(m_dist),abs(p_dist))
    ans = min(ans,dist_i)

print(ans)

### FIXED CODE ###

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

minus = 0
while minus < N and array[minus]<0:
    minus += 1

first,last = max(minus-K,0),min(minus,N-K)

ans = 2*(array[N-1]- array[0])

for i in range(first,last+1):
    m_dist, p_dist = array[i], array[K-1+i]
    if m_dist*p_dist <=0:
        dist_i = min(abs(m_dist),abs(p_dist))*2+max(abs(m_dist),p_dist)
    else:
        dist_i = max(abs(m_dist),abs(p_dist))
    ans = min(ans,dist_i)

print(ans)
N,X = map(int,input().split())
bound_limit= N+1
L = list(map(int,input().split()))
sum=0
count=1
for i in range(0,len(L)):
  sum+=L[i]
  if sum<=x:
    count+=1
  else:
    break
print(count)

### FIXED CODE ###

N,X = map(int,input().split())
bound_limit= N+1
L = list(map(int,input().split()))
sum=0
count=1
for i in range(0,len(L)):
  sum+=L[i]
  if sum<=X:
    count+=1
  else:
    break
print(count)
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n,k = map(int, input().split())
mod = 10 ** 9 + 7
for i in range(1,k+1):
  print((cmb(n-k+1,i) * cmb(k-1, i-1)) % mod)


### FIXED CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    if r > n: return 0
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n,k = map(int, input().split())
mod = 10 ** 9 + 7
for i in range(1,k+1):
  print((cmb(n-k+1,i) % mod * cmb(k-1, i-1) % mod) % mod)
X, Y, A ,B, C = list(map(int, input().split()))
P = list(map(int, input().split()))
P.sort(reverse = True)
P = P[:X]
Q = list(map(int, input().split()))
Q.sort(reverse = True)
Q = Q[:Y]
R = list(map(int, input().split()))
R.sort(reverse = True)
ans = 0
for i in range(C):
  if(P[-1] < Q[-1]):
    if(P[-1] < R[i]):
      ans += R[i]
      P.pop()
  else:
    if(Q[-1] < R[i]):
      ans += R[i]
      Q.pop()
    else:
      break
ans += sum(P) + sum(Q)
print(ans)

### FIXED CODE ###

X, Y, A ,B, C = list(map(int, input().split()))
P = sorted(list(map(int, input().split())), reverse = True)[:X]
Q = sorted(list(map(int, input().split())), reverse = True)[:Y]
R = sorted(list(map(int, input().split())), reverse = True)
ans = 0
for i in range(C):
  if(len(P) == 0):
    if(len(Q) == 0):
      break
    elif(Q[-1] < R[i]):
      Q.pop()
      ans += R[i]
    else:
      break
  elif(len(Q) == 0):
    if(P[-1] < R[i]):
      P.pop()
      ans += R[i]
    else:
      break
  else:
    if(P[-1] < Q[-1] and P[-1] < R[i]):
      P.pop()
      ans += R[i]
    elif(Q[-1] <= P[-1] and Q[-1] < R[i]):
      Q.pop()
      ans += R[i]
    else:
      break
ans += sum(P) + sum(Q)
print(ans)
import numpy as np

h, w = map(int, input().split())
grid = [[False for j in range(w)] for i in range(h)]

for i in range(h):
    grid = []
    for i in range(h):
        grid.append(list(input()))
    grid = (np.array(grid) == ".") * 1  # ランプをおける:1, 障害物:0

grid = np.array(grid)

L = np.zeros((h, w), dtype=int)
R = np.zeros((h, w), dtype=int)
U = np.zeros((h, w), dtype=int)
D = np.zeros((h, w), dtype=int)

for j in range(w):
    if j == 0:
        L[:, j] = grid[:, j]
    else:
        L[:, j] = (L[:, j - 1] + 1) * grid[:, j]


for j in range(w - 1, -1, -1):
    if j >= w - 1:
        R[:, j] = grid[:, j]
    else:
        R[:, j] = (R[:, j + 1] + 1) * grid[:, j]

for i in range(h):
    if i <= 0:
        U[i, :] = grid[i, :]
    else:
        U[i, :] = (U[i - 1, :] + 1) * grid[i, :]


for i in range(h - 1, -1, -1):
    if i >= h - 1:
        D[i, :] = grid[i, :]
    else:
        D[i, :] = (D[i + 1, :] + 1) * grid[i, :]

print(np.max(L + R + U + D - 3))


### FIXED CODE ###

import numpy as np

h, w = map(int, input().split())
grid = [[False for j in range(w)] for i in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == '.':
            grid[i][j] = 1
        else:
            grid[i][j] = 0

grid = np.array(grid)

L = np.zeros((h, w), dtype=int)
R = np.zeros((h, w), dtype=int)
U = np.zeros((h, w), dtype=int)
D = np.zeros((h, w), dtype=int)

for j in range(w):
    if j == 0:
        L[:, j] = grid[:, j]
    else:
        L[:, j] = (L[:, j - 1] + 1) * grid[:, j]


for j in range(w - 1, -1, -1):
    if j >= w - 1:
        R[:, j] = grid[:, j]
    else:
        R[:, j] = (R[:, j + 1] + 1) * grid[:, j]

for i in range(h):
    if i <= 0:
        U[i, :] = grid[i, :]
    else:
        U[i, :] = (U[i - 1, :] + 1) * grid[i, :]


for i in range(h - 1, -1, -1):
    if i >= h - 1:
        D[i, :] = grid[i, :]
    else:
        D[i, :] = (D[i + 1, :] + 1) * grid[i, :]

print(np.max(L + R + U + D - 3))
N = input()
d = [input() for i in range(N)]
print(len(set(d)) - 1)

### FIXED CODE ###

N = input()
d = [input() for i in range(int(N))]
print(len(set(d)))
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
a.reverse()
print(sum(0,k+1))

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
a.reverse()
print(sum(a[0:k]))
import sys

def prepare(X):
    N = 101
    List = [X] * N
    for i in range(0, 50):
        List[2*i+1] -= i+1
        List[2*i+2] += i+1
    return List

def remove(List, N, PList):
    for Num in range(N):
        List.pop( List.index(PList[Num]) )
    print(List[0])
if(__name__ == "__main__"):

    XY = input().strip().split()
    X = int(XY[0])
    N = int(XY[1])

    PList = [0] * N
    if(N > 0):
        P_str = input().strip().split()

        for i in range(N):
            PList[i] = int( P_str[i] )

        List = prepare(X)
        remove(List, N, PList)
    else:
        print(X)


### FIXED CODE ###

import sys

def prepare(X):
    N = 101
    List = [X] * N
    for i in range(0, 50):
        List[2*i+1] = X-i-1
        List[2*i+2] = X+i+1
    return List

def remove(List, N, PList):
    for Num in range(N):
        if(PList[Num] in List):
            List.pop( List.index(PList[Num]) )
    print(List[0])
if(__name__ == "__main__"):

    XY = input().strip().split()
    X = int(XY[0])
    N = int(XY[1])

    PList = [0] * N
    if(N > 0):
        P_str = input().strip().split()

        for i in range(N):
            PList[i] = int( P_str[i] )

        List = prepare(X)
        remove(List, N, PList)
    else:
        print(X)
num = int(input())
A = input().split(" ")
B = input().split(" ")
C = input().split(" ")
result = 0

for i in range(num):
  result += int(B[int(A[i])])
  if i > 0 and (int(A[i]) - int(A[i-1]) == 1):
    result += int(C[int(A[i-1])

print(result)

### FIXED CODE ###

num = int(input())
A = input().split(" ")
B = input().split(" ")
C = input().split(" ")
result = 0
 
for i in range(num):
  result += int(B[int(A[i])-1])
  if i > 0 and (int(A[i]) - int(A[i-1]) == 1):
    result += int(C[int(A[i])-2])
 
print(result)
# AtCoder Beginner Contest 126
# https://atcoder.jp/contests/abc126
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    uvw = ii2nnn(N-1)
    d = [[] for _ in range(N)]
    for u, v, w in uvw:
        b = w % 2 == 0
        d[u-1].append((v-1, b))
        d[v-1].append((u-1, b))
    nn = [-1 for _ in range(N)]
    nn[0] = 0
    def main2(src):
        links = d[src]
        c = nn[src]
        for dst, b in links:
            if nn[dst] == -1:
                nn[dst] = c if b else 1-c
                main2(dst)
    main2(0)
    for n in nn:
        print(n)

main()


### FIXED CODE ###

# AtCoder Beginner Contest 126
# https://atcoder.jp/contests/abc126
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    d = [[] for _ in range(N)]
    #uvw = ii2nnn(N-1)
    #for u, v, w in uvw:
    for _ in range(N-1):
        u, v, w = i2nn()
        b = w % 2 == 0
        d[u-1].append((v-1, b))
        d[v-1].append((u-1, b))
    nn = [-1 for _ in range(N)]
    nn[0] = 0
    def main2(src):
        links = d[src]
        c = nn[src]
        for dst, b in links:
            if nn[dst] == -1:
                nn[dst] = c if b else 1-c
                main2(dst)
    #main2(0)
    que = [0]
    que2 = []
    while True:
        if len(que) == 0:
            break
        que2 = []
        for src in que:
            links = d[src]
            c = nn[src]
            for dst, b in links:
                if nn[dst] == -1:
                    nn[dst] = c if b else 1-c
                    que2.append(dst)
        que = que2
    for n in nn:
        print(n)

main()
n,x=(int(i) for i in input().split())

def makeBurger(s):
    return "B"+s+"P"+s+"B"
s = "P"
for i in range(n):
    s = makeBurger(s)
count = 0
for i in range(x):
    if s[i]=='P':
        count += 1
print(count)

### FIXED CODE ###

n , x = map(int, input().split())
# ABCの長さ
a = [1]
for i in range(n):
    a.append(a[i] * 2 + 3)

# パティの枚数
p = [1]
for i in range(n):
    p.append(p[i] * 2 + 1)

def f(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    elif x == 1:
        return 0
    elif 1 <  x <=  1 + a[n - 1]:
        return f(n - 1, x - 1)
    elif x == 2 + a[n-1]:
        return p[n-1] + 1
    elif 2 + a[n - 1] < x <= 2 + 2 * a[n - 1]:
        return f(n - 1, x - 2 - a[n - 1]) + p[n-1] + 1
    elif x == 3 + 2 * a[n - 1]:
        return 2 * p[n-1] + 1

print(f(n, x))
n = int(input())
 s = input()
 ans = 0
 for i in range(n - 2):
     if s[i:i+3] == 'ABC':
         ans += 1 
 print(ans) 

### FIXED CODE ###

n = int(input())
s = input()

print(s.count('ABC'))
c = raw_input()

if c == "a" or "e" or "i" or "o" or "u":
  print ("vowel")
else:
  print ("consonant")


### FIXED CODE ###

c = input()

if c == "a" :
  print ("vowel")
elif c == "e" :
  print ("vowel")
elif c == "i" :
  print ("vowel")
elif c == "o" :
  print ("vowel")
elif c == "u" :
  print ("vowel")
else:
  print ("consonant")
N, Q = map(int, input().split())  # 複数数値入力
S = list(input())  # 一文字ずつ格納
L = []
R = []

for i in range(Q):
    l, r = map(int, input().split())  # 複数数値入力
    L.append(l)
    R.append(r)

list = []
flg = 0
for s in S:
    if s == "A":
        flg = 1
    elif s == "C" and flg == 1:
        list.append(1)
        list.append(2)
        flg = 0
    elif flg == 1:
        list.append(0)
        list.append(0)
    else:
        list.append(0)

for i in range(Q):
    S = list[L[i]-1:]
    S = S[:R[i] - L[i]+1]
    if S[0] == 2:
        S = S[1:]
    if S[-1] == 1:
        S = S[:-2]
    print(int(sum(S)/3))


### FIXED CODE ###

import numpy as np

N, Q = map(int, input().split())  # 複数数値入力
S = list(input())  # 一文字ずつ格納

dp = [0] * N
i = 0
flg = False
for str in S:
    if str == "C" and flg == True:
        dp[i] = dp[i - 1] + 1
        flg = False
    elif str == "A":
        flg = True
        dp[i] = dp[i-1]
    else:
        flg = False
        dp[i] = dp[i-1]
    i += 1

for i in range(Q):
    l, r = map(int, input().split())  # 複数数値入力
    print(dp[r-1]-dp[l-1])
a = int(input())
b = int(input())
if 0 <= a and  a <= 5:
    print(0)
if 6 <= a  and a <= 12:
    print(b//2)
if 16 <= a and a <= 100:
    print(b)

### FIXED CODE ###

a, b = [int(x) for x in input().split()]

cost = 0
if a >= 13:
    cost = b
elif a >= 6:
    cost = b / 2
else:
    cost = 0

print(int(cost))
a, b = map(int, input().split())
if a >= b + 1:
  print(a + a -1)
elif a = b:
  print(a + b)
else:
  print(b + b - 1)

### FIXED CODE ###

a, b = map(int, input().split())
if a > b :
  print(a + a -1)
elif a == b:
  print(a + b)
else:
  print(b + b - 1)
#!/mnt/c/Users/moiki/bash/env/bin/python
N,X = map(int, input().split())
A = list(map(int, input().split()))
A = [ abs(a-X) for a in A]
import math
from functools import reduce

print( reduce(math.gcd, A) )



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# import math
from functools import reduce
def gcd(m, n):
  while n:
    m, n = n, m%n
  return m

N,X = map(int, input().split())
A = list(map(int, input().split()))
A = [ abs(a-X) for a in A]

print( reduce(gcd, A) )
s = input()
dp = [0]*(len(s)-3)
for i in range(4, len(s)):
    dp[i-3] = dp[i-4]
    for j in range(i-3):
        if not int(s[j:i+1])%2019: dp[i-3]+=1
print(dp[-1])

### FIXED CODE ###

s = input()
counter = [0]*2019
counter[0] = 1
ans = 0
res, d = 0, 1
for i in range(len(s)-1, -1, -1):
    res = (res+int(s[i])*d)%2019
    counter[res] += 1
    d = d*10%2019
for count in counter:
    ans += count*(count-1)//2
print(ans)
from functools import reduce
from fractions import gcd

n = int(input())
As = list(map(int, input().split()))
mod = 10**9 + 7
def lcm(l):
    if len(l) == 2:
        return l[1]*l[0] // gcd(l[1], l[0])
    else:
        k = lcm(l[:-1])
        return k*l[-1] // gcd(k, l[-1])

k = lcm(As)
ans = 0
for i in range(n):
    ans += k // As[i]
    ans %= mod
print(ans)

### FIXED CODE ###

from functools import reduce
from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers)
mod = 10**9 + 7
n = int(input())
As = list(map(int, input().split()))

lcm = lcm_list(As)
b = [lcm//As[i] for i in range(n)]

print(sum(b) % mod)
a,p ＝ map(int, input().split())
print((a * 3 + p) // 2)


### FIXED CODE ###

a,p = map(int, input().split())
print((a*3+p)//2)
inf = float('inf')

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

# 累積min/max
cmin = [0] * (N+1)
cmax = [0] * (N+1)
resmin = inf
resmax = -inf
for i, a in enumerate(A):
    resmin = min(resmin, a)
    resmax = max(resmax, a)
    cmin[i+1] = resmin
    cmax[i+1] = resmax

# 正負の境界を全探索 -[0,k) +[k, N)
for k in range(N+1):
    ans = []
    cnt = 0
    m = cmin[k]
    M = cmax[N] - cmax[k]

    if m < 0:
        for i, a in enumerate(A):
            res = max(-(a // m), 0)
            cnt += res
            if cnt > 2*N:
                break
            for _ in range(res):
                x = A.index(m)
                y = i
                A[y] += A[x]
                ans.append((x, y))
        
        for i in range(k-1, 0, -1):
            ans.append((i, i-1))
            A[i-1] += A[i]
            cnt += 1

    if M > 0:
        for i, a in enumerate(A):
            res = max(-(a // M), 0)
            cnt += res
            if cnt > 2*N:
                break
            for _ in range(res):
                x = A.index(M)
                y = i
                A[y] += A[x]
                ans.append((x, y))

        for i in range(k, N-1):
            ans.append((i, i+1))
            A[i+1] += A[i]
            cnt += 1
    
    flag = all(A[i] <= A[i+1] for i in range(N-1))

    if cnt < 2*N and flag:
        print(cnt)
        for x, y in ans:
            print(x+1, y+1)
        exit()

### FIXED CODE ###

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

M = max(A)
Mi = A.index(M)
m = min(A)
mi = A.index(m)

cnt = 0
ans = []

if M > 0 and m < 0:
    if abs(m) <= abs(M):
        for i in range(N):
            if Mi == i:
                continue
            x = Mi
            y = i
            A[y] += A[x]
            ans.append((x, y))
            cnt += 1
    else:
        for i in range(N):
            if mi == i:
                continue
            x = mi
            y = i
            A[y] += A[x]
            ans.append((x, y))
            cnt += 1

M = max(A)
m = min(A)

if m >= 0:
    for i in range(N-1):
        x = i
        y = i+1
        A[y] += A[x]
        ans.append((x, y))
        cnt += 1
else:
    for i in range(N-1, 0, -1):
        x = i
        y = i-1
        A[y] += A[x]
        ans.append((x, y))
        cnt += 1

print(cnt)
for x, y in ans:
    print(x+1, y+1)
s = print()
p = print()

s *= 2
if s.find(p) ! = -1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input()
p = input()

s *= 2
if s.find(p) != -1:
    print("Yes")
else:
    print("No")
from itertools import permutations

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

cnt=0
for v in permutations(range(1,N+1), N):
    cnt +=1
    if(p==v):
        a = cnt
    if(q==v):
        b = cnt

print(abs(a-b))

### FIXED CODE ###

import itertools
n = int(input())
p = tuple(((map(int,input().split()))))
q = tuple(((map(int,input().split()))))

num = []
for i in range(1,n+1):
    num.append(i)
ans = []
for i in itertools.permutations(num,n):
    ans.append(i)

print(abs(ans.index(p)-ans.index(q)))
N,K=map(int,input().split())
S=input()
for i,m in enumerate(S):
    if m=="A":
        S[i]="A"
    if m=="B":
        S[i]="B"
    if m=="C"
        S[i]="C"
print(S)


### FIXED CODE ###

N,K=map(int,input().split())
S=input()
SS=""
for i,s in enumerate(S):
    if i==K-1:
        if s=="A":
            s="a"
        if s=="B":
            s="b"
        if s=="C":
            s="c"
    SS+=s
print(SS)
a,b=map(int.input(),split())
if a-b＊2<=0:
  
  print(0)
else:
  print(a-b＊2)
  


### FIXED CODE ###

a,b=map(int,input().split())
if a-b*2<=0:
  
  print(0)
else:
  print(a-b*2)
a = int(input())
b = int(input())

c = (a - b) % 2 
if c == 0:
  abs_a = abs(a)
  abs_b = abs(b)

  m = (max(abs_a, abs_b) - min(abs_a, abs_b)) /2
  ans = max(abs_a, abs_b) - m
  print(ans)
else:
  print("IMPOSSIBLE")

### FIXED CODE ###

inp = input().split(" ")
a = int(inp[0])
b = int(inp[1])
 
c = (a - b) % 2 
if c == 0:
  abs_a = abs(a)
  abs_b = abs(b)
 
  m = (max(abs_a, abs_b) - min(abs_a, abs_b)) /2
  ans = max(abs_a, abs_b) - m
  print(int(ans))
else:
  print("IMPOSSIBLE")