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

h,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
 
dp=[0]*h
for i in range(h):
    _min = 10**10
    for g in range(n):
        if i>=ab[g][0]:
            _min = min(ab[g][1]+dp[i-ab[g][0]], _min)
        else:
            _min = min(ab[g][1], _min)
    dp[i]=_min
print(dp[-1])

### FIXED CODE ###

h,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]

dp=[0]*h
for i in range(h):
    _min = 10**10
    for g in range(n):
        if i>=ab[g][0]:
            _min = min(ab[g][1]+dp[i-ab[g][0]], _min)
        else:
            _min = min(ab[g][1], _min)
    dp[i]=_min
print(dp[-1])
### BUGGY CODE ###

k, s = list(map(int, input().split()))


def Weight(x, y, z):
    if len({x, y, z}) == 1:
        return 1
    elif len({x, y, z}) == 2:
        return 3
    elif len({x, y, z}) == 3:
        return 6


counter = 0
for x in range(k+1):
    for y in range(x+1):
        for z in range(y+1):
            if x + y + z == s:
                counter += Weight(x, y, z)

print(counter)

### FIXED CODE ###

k, s = list(map(int, input().split()))


counter = 0
for x in range(k+1):
    for y in range(k+1):
        if 0 <= s - x - y <= k:
            counter += 1

print(counter)
### BUGGY CODE ###

from math import gcd

n = int(input())

gcd_dic = {}
ans = 0
for i in range(1, n + 1):
    if i == 1:
        ans += n ** 2
        continue
    for j in range(1, n + 1):
        if i == 1:
            ans += n
            continue
        for k in range(1, n + 1):
            if i == 1:
                ans += 1
                continue
            comb = tuple(sorted([i, j, k]))
            if comb not in gcd_dic:
                gcd_dic[comb] = gcd(gcd(i, j), k)
            ans += gcd_dic[comb]
print(ans)

### FIXED CODE ###

answer = [1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692]
n = int(input())
print(answer[n - 1])
### BUGGY CODE ###

import networkx as nx

MAX = 10 ** 15
N, M, S, T = map(int, input().split())

G = nx.Graph()
G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    u, v, a, b = map(int, input().split())
    G.add_edge(u, v, yen=a, snuuk=b)

yen_path = nx.single_source_dijkstra_path_length(G, S, weight='yen')
snuuk_path = nx.single_source_dijkstra_path_length(G, T, weight='snuuk')

ans = [MAX] * (N + 1)
for i in range(N, 0, -1):
    ans[i - 1] = min(ans[i], yen_path[i] + snuuk_path[i])
for x in ans[:N]:
    print(MAX - x)


### FIXED CODE ###

import sys
import networkx as nx

input = sys.stdin.buffer.readline

MAX = 10 ** 15
N, M, S, T = map(int, input().split())

G = nx.Graph()
G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    u, v, a, b = map(int, input().split())
    G.add_edge(u, v, yen=a, snuuk=b)

yen_path = nx.single_source_dijkstra_path_length(G, S, weight='yen')
snuuk_path = nx.single_source_dijkstra_path_length(G, T, weight='snuuk')

ans = [MAX] * (N + 1)
for i in range(N, 0, -1):
    ans[i - 1] = min(ans[i], yen_path[i] + snuuk_path[i])
for x in ans[:N]:
    print(MAX - x)
### BUGGY CODE ###

S = input()
ans = len(S)
while 'ST' in S:
    num = S.count('ST')
    S = S.replace('ST','',num)


print(len(S))


### FIXED CODE ###

S = input()
ans = len(S)

stack = []
for s in S:

    if s == 'S':
        stack.append(s)
    elif s == 'T' and len(stack) == 0 or stack[-1] == 'T':
        stack.append(s)
    elif s == 'T' and stack[-1] == 'S':
        stack.pop()

print(len(stack))

# #部分点
# while 'ST' in S:
#     num = S.count('ST')
#     S = S.replace('ST','',num)

#print(len(S))
### BUGGY CODE ###

# coding: utf-8
from collections import deque
N = int(input())
S = input()
Sd = deque(S)
ans = 0
R, G, B = 0, 0, 0
for i in range(N):
    p = Sd.popleft()
    if p == "R":
        R += 1
    elif p == "G":
        G += 1
    else:
        B += 1
ans = R * G * B
for i in range(N):
    for d in range(N):
        j = i + d
        k = j + d
        if k >= N:
            continue
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1
print(ans)

### FIXED CODE ###

# coding: utf-8
from collections import deque
N = int(input())
S = input()
Sd = deque(S)
ans = 0
R, G, B = 0, 0, 0
for i in range(N):
    p = Sd.popleft()
    if p == "R":
        R += 1
    elif p == "G":
        G += 1
    else:
        B += 1
ans = R * G * B
for i in range(N):
    for d in range(N):
        j = i + d
        k = j + d
        if k >= N:
            continue
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            ans -= 1
print(ans)
### BUGGY CODE ###

n= int(input())

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

for i in range(n):
	a=list.count(i+1)
	print(a)


### FIXED CODE ###

n = int(input())
lis = list(map(int, input().split()))
cnt = [0]*(n)

for i in range(n-1):
	cnt[lis[i]-1]+=1

for i in range(n):
	print(cnt[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
result_1 = []
result_1.append(abs(a[0]))
for i in range(n-1):
    result_1.append(abs(a[i+1]-a[i]))
result_1.append(abs(a[n-1]))
a.insert(0,0)
a.insert(n+1,0)
for i in range(n):
    b = abs(a[i+2]-a[i+1])
    c = abs(a[i+1]-a[i])
    d = abs(a[i+2]-a[i])
    result = sum(result_1) - (b + c - d)
    print(result)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
total = abs(a[0]) + abs(a[n-1])
for i in range(n-1):
    total += abs(a[i+1] - a[i])
a.insert(0,0)
a.insert(n+1,0)
ans=[]
for i in range(1,n+1):
    if a[i-1]<=a[i]<=a[i+1] or a[i-1]>=a[i]>=a[i+1]:
        ans.append(total)
    else:
        change = total + abs(a[i+1]-a[i-1]) -(abs(a[i]-a[i-1])+abs(a[i+1]-a[i]))
        ans.append(change)
for i in range(n):
    print(ans[i])
### BUGGY CODE ###

import numpy


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

max=0

A.insert(0, 0)
A = numpy.cumsum(A)
B.insert(0,0)



for i in range(N+1):
    hp=K
    hp-=A[i]

    if hp < 0:
        break

    for j in range(M+1):
        hp-=B[j]

        if hp < 0:
            break

        if max < i+j :
            max = i+j

print(max)



### FIXED CODE ###

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

a,b=[0],[0]
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])

ans,j=0,M

for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j-=1
    
    ans = max(ans,i+j)

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

def solve(way, height, n):
  ss = set()
  for a,b in way:
    if height[a-1] <= height[b-1]:
      ss = ss | {a}
    if height[a-1] >= height[b-1]:
      ss = ss | {b}
  return n - len(ss)


if __name__ == "__main__":
  n,m = map(int, input().split())
  height = [int(i) for i in input().split()]
  way = [tuple(map(int, input().split())) for i in range(m)]
  print(solve(way, height, n))


### FIXED CODE ###

def solve(way, height, n):
  ss = []
  for a,b in way:
    if height[a-1] <= height[b-1]:
      ss.append(a)
    if height[a-1] >= height[b-1]:
      ss.append(b)
  return n - len(set(ss))


if __name__ == "__main__":
  n,m = map(int, input().split())
  height = [int(i) for i in input().split()]
  way = [tuple(map(int, input().split())) for i in range(m)]
  print(solve(way, height, n))
### BUGGY CODE ###

N = int(input())
list = []
for i in range(N):
    i = int(input())
    if i not in list:
        list.append(i)
    elif i in list:
        list.remove(i)
print(len(list))

### FIXED CODE ###

N = int(input())
list = set()
for i in range(N):
    i = int(input())
    if i not in list:
        list.add(i)
    elif i in list:
        list.remove(i)
print(len(list))
### BUGGY CODE ###

import itertools
h, w = map(int, input().split())
map_lst = []
for i in range(h):
    map_lst.append(list(input()))
#0:下 1:右
lst = [i for i in range(h + w - 2)]
lst = list(itertools.combinations(lst,h-1))
ans = 200
for i in lst:
    rc_lst = [1] * (h + w - 2)
    for j in i:
        rc_lst[j] = 0
    bw_lst = []
    if map_lst[0][0] == '.': bw_lst.append(0)
    elif map_lst[0][0] == '#': bw_lst.append(1)
    r = 0
    c = 0
    cnt_b = 0
    # print(rc_lst)
    for j in range(h + w - 2):
        if rc_lst[j] == 0: r += 1
        elif rc_lst[j] == 1: c += 1
        if map_lst[r][c] == ".":
            if bw_lst[-1] == 1:
                cnt_b += 1
            bw_lst.append(0)
        elif map_lst[r][c] == "#":
            bw_lst.append(1)
    if map_lst[h-1][w-1] == '#': cnt_b += 1
    ans = min(ans, cnt_b)
    # print(rc_lst, bw_lst, cnt_b)
print(ans)

### FIXED CODE ###

import itertools
h, w = map(int, input().split())
map_lst = []
for i in range(h):
    map_lst.append(list(input()))
dp = [[200] * (w) for i in range(h)]
if map_lst[0][0] == '.': dp[0][0] = 0
else: dp[0][0] = 1
# for i in dp:
#     print(i)
for c in range(w):
    for r in range(h):
        over = 0
        left = 0
        if r > 0:
            if map_lst[r-1][c] == '.' and map_lst[r][c] == '#':
                over = 1
        if c > 0:
            if map_lst[r][c-1] == '.' and map_lst[r][c] == '#':
                left = 1
        if r == 0 and c == 0:
            continue
        elif r == 0:
            dp[r][c] = dp[r][c-1] + left
        elif c == 0:
            dp[r][c] = dp[r-1][c] + over
        else:
            dp[r][c] = min(dp[r-1][c] + over, dp[r][c-1] + left)
# for i in dp:
#     print(i)
print(dp[-1][-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N + 1):
  print(A.count(i))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0 for i in range(N)]
for a in A:
  ans[a - 1] += 1
for a in ans:
  print(a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
N, M = map(int, input().split())
L = []
for _ in range(M) :
  L.append(list(map(str, input().split())))
#print(L)
  
D = {}
for i in range(M) :
  if L[i][0] not in D :
    D[L[i][0]] = L[i][1]
  else :
    if L[i][1] == "AC" :
      D[L[i][0]] = L[i][1]

ACsum = 0
ACList = []
for mykey, myvalue in D.items() :
  if myvalue == "AC" :
    ACsum += 1
    ACList += [mykey]
    
#print(ACList)
WAsum = 0
for k in range(len(ACList)) :
  for i in range(M) :
    #print(ACList[k])
    #print(L[i][0])
    #print(L[i][1])
    if ACList[k] == L[i][0] :
      if L[i][1] == "WA" :
        WAsum += 1
      else :
        break

print(str(ACsum) + " " + str(WAsum))

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
N, M = map(int, input().split())
L = []
for _ in range(M) :
  L.append(list(map(str, input().split())))
#print(L)

A = [[0 for _ in range(2)] for _ in range(N+1)]

for i in range(M) :
  if L[i][1] == "WA" and A[int(L[i][0])][1] != 1:
    A[int(L[i][0])][0] += 1
  else :
    A[int(L[i][0])][1] = 1

#print (A)
ACsum = 0
WAsum = 0
for j in range(N+1) :
  if A[j][1] == 1 :
    ACsum += 1
    WAsum += A[j][0]
  
print(str(ACsum) + " " + str(WAsum))
### BUGGY CODE ###

from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math
import bisect

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,k = readInts()
p = [0]
p.extend(readInts())
c = [0]
c.extend(readInts())

score = [[0]]
for i in range(1,n+1):
	t = [0]
	al = []
	j = p[i]
	while j not in al:
		t.append(t[-1]+c[j])
		al.append(j)
		j = p[j]
	score.append(t)

ans = -1*float("inf")
for i in range(1,n+1):
	tar = score[i]
	if tar[-1]<0:
		ans = max(ans, max(tar[1:k+1]))
	else:
		kuri = k//(len(tar)-1)
		t = kuri*tar[-1]
		ans = max(ans, max(t,t+max(tar[:k-kuri*(len(tar)-1)+1])))

print(ans)


### FIXED CODE ###

from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,k = readInts()
p = [0]+readInts()
c = [0]+readInts()

ans = -1*float("inf")
for i in range(1,n+1):
	j = p[i]
	t = [0]
	al = set()
	while j not in al:
		t.append(t[-1]+c[j])
		al.add(j)
		j = p[j]
	if t[-1]<=0:
		ans = max(ans, max(t[1:k+1]))
	else:
		kuri =(k-1)//(len(t)-1)
		s = kuri*t[-1]
		re = k -kuri*(len(t)-1)
		ans = max(ans, max(s,s+max(t[:re+1])))

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

N = list(map(int, input().split()))
H = list(map(int, input().split()))
B = [list(map(int, input().split())) for i in range(N[1])]

# N = [6, 5]
# H = [8, 6, 9, 1, 2, 1]
# B = [[1, 3], [4, 2], [4, 3], [4, 6], [4, 6]]

counter = N[0]
for i in range(N[0]):
    for b in B:
        if (b[0]-1 == i and H[b[1]-1] >= H[i]) or (b[1]-1 == i and H[b[0]-1] >= H[i]):
            counter += -1
            break

print(counter)

### FIXED CODE ###

N = list(map(int, input().split()))
H = list(map(int, input().split()))
B = [list(map(int, input().split())) for i in range(N[1])]

# N = [6, 5]
# H = [8, 6, 9, 1, 2, 1]
# B = [[1, 3], [4, 2], [4, 3], [4, 6], [4, 6]]

# N = [4, 3]
# H = [1, 2, 3, 4]
# B = [[1, 3],[2, 3],[2, 4]]

counter = [1 for i in range(N[0])]

for b in B:
    if H[b[1]-1] > H[b[0]-1]:
        counter[b[0]-1] = 0
    elif H[b[0]-1] > H[b[1]-1]:
        counter[b[1]-1] = 0
    elif H[b[0]-1] == H[b[1]-1]:
        counter[b[0]-1] = 0
        counter[b[1]-1] = 0

print(sum(counter))
### BUGGY CODE ###

# coding: utf-8
N = int(input())
S = input()
ans = 0
for v in range(1000):
    v = str(v).zfill(3)
    flag = [False for _ in range(3)]
    for i in range(len(S)):
        if not flag[0] and v[0] == S[i]:
            flag[0] = True
            continue
        if not flag[1] and v[1] == S[i]and flag[0]:
            flag[1] = True
            continue
        if not flag[2] and v[2] == S[i] and flag[1]:
            flag[2] = True
            break
    if sum(flag) == 3:
        ans += 1
print(ans)

### FIXED CODE ###

# coding: utf-8
N = int(input())
S = input()
ans = []
for v in range(1000):
    used = [False for _ in range(len(S))]
    v = str(v).zfill(3)
    idx = 0
    for i in range(len(S)):
        if v[0] == S[i] and not used[i]:
            used[i] = True
            idx = i + 1
            break
    for i in range(idx, len(S)):
        if v[1] == S[i] and not used[i]:
            used[i] = True
            idx = i + 1
            break
    for i in range(idx, len(S)):
        if v[2] == S[i] and not used[i]:
            used[i] = True
            break
    if sum(used) == 3 and v not in ans:
        ans.append(v[:])
print(len(ans))
### BUGGY CODE ###

def number(m,l):
  count=0
  for i in range(m):
    if min(l[:i+1])==l[i]:
      count+=1
  return count

n=int(input())
p=list(map(int,input().split()))
result=number(n,p)
print(result)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
count=0
min=1000000
for i in range(n):
  if p[i]<=min:
    count+=1
    min=p[i]
  
print(str(count))
### BUGGY CODE ###

from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
N = [[0, 1], [0, -1], [1, 0], [-1, 0]]
P = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
     [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in N:
        if 0 <= x + NX < w and 0 <= y + NY < h and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for PY, PX in P:
        if 0 <= x + PX < w and 0 <= y + PY < h and S[y + PY][x + PX] != '#':
            if grid[y + PY][x + PX] == -1 or grid[y + PY][x + PX] > count + 1:
                grid[y + PY][x + PX] = count + 1
            que.append((count + 1, y + PY, x + PX))

print(grid[dh][dw])


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [list(input()) for _ in range(h)]

Ch, Cw = Ch - 1, Cw - 1
Dh, Dw = Dh - 1, Dw - 1
d = [[-1] * w for _ in range(h)]
d[Ch][Cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2], [0, -2], [-1, 2], [-1, 1],
        [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

que = deque([[0, Ch, Cw]])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft([count, y + NY, x + NX])
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append([count + 1, y + NY, x + NX])

print(d[Dh][Dw])
### BUGGY CODE ###

N = int(input())
A = [int(s) for s in input().split()]
Q = int(input())
B = []
C = []
for _ in range(Q):
    b, c = [int(s) for s in input().split()]
    B.append(b)
    C.append(c)

for b, c in zip(B, C):
    A = list(map(lambda x: c if x == b else x, A))
    ans = sum(A)
    print(ans)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
A = [int(s) for s in input().split()]
Q = int(input())
B = []
C = []
for _ in range(Q):
    b, c = [int(s) for s in input().split()]
    B.append(b)
    C.append(c)

A_dict = defaultdict(int)
for a in A:
    A_dict[a] += 1

A_sum = sum(A)
for b, c in zip(B, C):
    n = A_dict[b]
    A_dict[b] = 0
    A_dict[c] += n
    A_sum += (c - b) * n
    print(A_sum)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
left = 0
ans = 1
l = 1
pre = A[0]
right = 1
while N > 1:
    if right >= N:
        N -= 1
        A.pop(left)
        l = 1
        ans += 1
        right = left+1
        pre = A[left]
    elif pre < A[right]:
        l += 1
        pre = A.pop(right)
        N -= 1
    else:
        right += 1
print(ans)


### FIXED CODE ###

import bisect
def LIS():
    L[0] = A[0]
    length = 1
    for i in range(1, N):
        if L[length-1] < A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_left(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

def LISDesc():
    L[0] = A[-1]
    length = 1
    for i in range(N-2, -1, -1):
        if L[length-1] <= A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_right(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

INFTY = 10**13
N = int(input())
A = [int(input()) for i in range(N)]
L = [INFTY for i in range(N)]
ans = LISDesc()
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    s = list(str(n))
    s.reverse()
    s = [int(c) for c in s]
    s += [0]
    m = len(s)

    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            if dp[i+1][0] >= dp[i][j]+nd:
                dp[i+1][0] = dp[i][j]+nd
            if dp[i+1][1] >= dp[i][j]+10-nd:
                dp[i+1][1] = dp[i][j]+10-nd
    #print(dp)
    print(dp[m][0])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = list(str(input()))
    s.reverse()
    for i in range(len(s)):
        s[i] = int(s[i])
    s += [0]
    m = len(s)

    dp = [[10**7, 10**7] for _ in range(len(s)+5)]
    # dp[i][0]: 繰り下がりなし
    # dp[i][1]: 繰り下がりあり

    dp[0][0] = 0

    for i in range(m):
        for j in range(2):
            nd = s[i]
            if j == 1:
                nd += 1
            if dp[i+1][0] >= dp[i][j]+nd:
                dp[i+1][0] = dp[i][j]+nd
            if dp[i+1][1] >= dp[i][j]+10-nd:
                dp[i+1][1] = dp[i][j]+10-nd
    #print(dp)
    print(dp[m][0])

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

import math
import functools
import fractions
from functools import reduce
import itertools

gcd1 = 0
gcd2 = 0
ans = 0

N = int(input())
values = ([int(x) for x in input().split()])
for i in range(len(values)):
  tem = values.pop(i)
  gcd1 = functools.reduce(fractions.gcd,values)
  values.insert(i,tem)
  if gcd1>gcd2:
    gcd2 = gcd1
    ans = gcd1
    
print(ans)

### FIXED CODE ###

import fractions
N = int(input())
values = ([int(x) for x in input().split()])

gcd_from_the_left = []
gcd_from_the_left.append(values[0])
for i in range(N):
	gcd_from_the_left.append(fractions.gcd(gcd_from_the_left[i],values[i]))
gcd_from_the_left.pop(0)

gcd_from_the_right = []
gcd_from_the_right.append(values[-1])
for i in range(N):
	gcd_from_the_right.append(fractions.gcd(gcd_from_the_right[i],values[-i-1]))

gcd_from_the_right.pop(0)

ans = 0
gcd = 0

for i in range(N-2):
  gcd = fractions.gcd(gcd_from_the_left[i],gcd_from_the_right[N-i-3])
  if gcd > ans:
    ans = gcd
    
gcd = gcd_from_the_left[-2]
if gcd > ans:
  ans = gcd
gcd = gcd_from_the_right[-2]
if gcd > ans:
  ans = gcd
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
cnt0=[0]*60
cnt1=[0]*60
mod=10**9+7
tp=[0]*60
for i in range(60):
  tp[i]=(1<<i)%mod
for i in a:
  for j in range(60):
    if (i>>j)&1:
      ans+=(cnt0[j]*tp[j])
      if ans>=mod:
        ans%=mod
    else:
      ans+=(cnt1[j]*tp[j])
      if ans>=mod:
        ans%=mod
  for j in range(60):
    if (i>>j)&1:
      cnt1[j]+=1
    else:
      cnt0[j]+=1
if ans>=mod:
  ans%=mod
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
cnt0=[0]*60
cnt1=[0]*60
mod=10**9+7
tp=[0]*60
for i in range(60):
  tp[i]=(1<<i)%mod
for i in range(60):
    x=1<<i
    one=sum(1 for j in a if j&x)
    ans+=tp[i]*one*(n-one)
print(ans%mod)