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

n, m = [int(_) for _ in input().split()]
c = []
flag = True
for i in range(m):
    l, r, d = [int(_) for _ in input().split()]
    l_in = False
    r_in = False
    for j in range(len(c)):
        c_tmp = [_[0] for _ in c[j]]
        if l in c_tmp and r in c_tmp:
            if c[j][c_tmp.index(r)][1] - c[j][c_tmp.index(l)][1] != d:
                flag = False
                break
        elif l in c_tmp:
            l_in = True
            l_group = j
            l_pos = c[j][c_tmp.index(l)][1]
        elif r in c_tmp:
            r_in = True
            r_group = j
            r_pos = c[j][c_tmp.index(r)][1]
    if l_in and r_in:
        for j in range(len(c[r_group])):
            c[r_group][j][1] += l_pos + d - r_pos
        c[l_group].extend(c[r_group])
        del c[r_group]
    elif l_in:
        c[l_group].append([r, l_pos+d])
    elif r_in:
        c[r_group].append([l, r_pos-d])
    else:
        c.append([[l, 0], [r, d]])

    if not flag:
        break

if flag:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n, m = [int(_) for _ in input().split()]
c = []
flag = True
g = [[-1, -1] for _ in range(n)]
g_num = 0
for i in range(m):
    l, r, d = [int(_) for _ in input().split()]
    l -= 1
    r -= 1
    if g[l][0] != -1 and g[r][0] != -1 and g[l][0] == g[r][0]:
        if c[g[l][0]][g[r][1]][1] - c[g[l][0]][g[l][1]][1] != d:
            flag = False
            break
    elif g[l][0] != -1 and g[r][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        r_pos = c[g[r][0]][g[r][1]][1]
        if r_pos > l_pos+d:
            for j in c[g[l][0]]:
                j[1] += r_pos - d - l_pos
                if j[1] > 10**9:
                    flag = False
                    break
                g[j[0]][1] += g[c[g[r][0]][-1][0]][1] + 1
            c[g[r][0]].extend(c[g[l][0]])
            for j in c[g[l][0]]:
                g[j[0]][0] = g[r][0]

        else:
            for j in c[g[r][0]]:
                j[1] += l_pos + d - r_pos
                if j[1] > 10**9:
                    flag = False
                    break
                g[j[0]][1] += g[c[g[l][0]][-1][0]][1] + 1
            c[g[l][0]].extend(c[g[r][0]])
            for j in c[g[r][0]]:
                g[j[0]][0] = g[l][0]

    elif g[l][0] != -1:
        l_pos = c[g[l][0]][g[l][1]][1]
        c[g[l][0]].append([r, l_pos+d])
        g[r][0] = g[l][0]
        g[r][1] = g[c[g[l][0]][-2][0]][1]+1
    elif g[r][0] != -1:
        r_pos = c[g[r][0]][g[r][1]][1]
        c[g[r][0]].append([l, r_pos-d])
        g[l][0] = g[r][0]
        g[l][1] = g[c[g[r][0]][-2][0]][1]+1
    else:
        c.append([[l, 0], [r, d]])
        g[l][0] = g_num
        g[r][0] = g[l][0]
        g[l][1] = 0
        g[r][1] = 1
        g_num += 1
    if not flag:
        break
if flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

class RmaxQ:
    def __init__(self, original):
        self.n = len(original)
        self.INF = -(2**31)
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = max(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            if y >= x:
                break
            i >>= 1
            self.seg[i] = x
                

    def add(self, i, d):
        self.update(i, self.get(i)+d)

    def query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = max(res, self.seg[r-1])
            if l & 1:
                res = max(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res
        
n = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = RmaxQ([0]*(n+1))
for i in range(n):
  h, a = H[i], A[i]
  dp.update(h, max(dp.get(h), dp.query(0, h)+a))
ans = dp.query(0, n+1)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

class RmaxQ:
    def __init__(self, original):
        self.n = len(original)
        self.INF = -(2**31)
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = max(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            if y >= x:
                break
            i >>= 1
            self.seg[i] = x
                

    def add(self, i, d):
        self.update(i, self.get(i)+d)

    def query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = max(res, self.seg[r-1])
            if l & 1:
                res = max(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res
        
n = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = RmaxQ([0]*(n+1))
for i in range(n):
  h, a = H[i], A[i]
  dp.update(h, max(dp.get(h), dp.query(0, h)+a))
ans = dp.query(0, n+1)
print(ans)
### BUGGY CODE ###

from collections import deque

N,M = [int(x) for x in input().split()]
next =[set() for _ in range(N+1)]

for i in range(M):
    A,B = [int(x) for x in input().split()]
    next[A].add(B)
    next[B].add(A)

opened = deque()
opened.append(1)

closed = set()
prev = [-1] * (N+1)
prevlen = [float('inf')] * (N+1)
prevlen[1] = 0

while len(opened) != 0:
    target = opened.popleft()
    closed.add(target)
    for n in next[target]:
        if n not in closed:
            opened.append(n)
        if prevlen[n] > prevlen[target]+1:
            prev[n] = target
            prevlen[n] = prevlen[target]+1


print('Yes')
for i in range(2,N+1):
    print(prev[i])

### FIXED CODE ###

from sys import stdin
input = stdin.readline
from collections import deque

N,M = [int(x) for x in input().split()]
next =[set() for _ in range(N+1)]

for i in range(M):
    A,B = [int(x) for x in input().split()]
    next[A].add(B)
    next[B].add(A)

opened = deque()
opened.append(1)

prev = [-1] * (N+1)
prev[1] = 1

while len(opened) != 0:
    target = opened.popleft()
    for n in next[target]:
        if prev[n] == -1:
            opened.append(n)
            prev[n] = target


print('Yes')
# for i in range(2,N+1):
#     print(prev[i])
print(" ".join([str(x) for x in prev[2:]]))
### BUGGY CODE ###

N, M = map(int,input().split())
LR = [list(map(int,input().split())) for _ in range(M)]

cnt = 0
for i in range(N):
  tmp = 0
  for L, R in LR:
    if L-1 <= i <= R-1:
      tmp += 1
    if tmp == M:
      cnt += 1
      break
print(cnt)

### FIXED CODE ###

N, M = map(int,input().split())
LR = [list(map(int,input().split())) for _ in range(M)]

Lma = 0
Rmi = N + 1
for L, R in LR:
  Lma = max(L, Lma)
  Rmi = min(R, Rmi)

print(max(0, Rmi - Lma + 1))
### BUGGY CODE ###

import collections
N = int(input())
S = [input() for i in range(N)]
c = collections.Counter(S)
a = list(c.items())
b = list(c.values())

list1 =sorted( [kv[0] for kv in a if kv[1] == max(b)])
for i in range(len(list1)):
  print(list1[i])

### FIXED CODE ###

N = int(input())
dic = {}

for i in range (N):
  s = input()
  if s in dic:
    dic[s] += 1
  else:
    dic[s] = 1

sai = max(dic.values())

for j in sorted(k for k in dic if dic[k] == sai):
  print(j)
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

n,m,s,t = II()
u,v,a,b = Line(m)

from heapq import heappop, heappush
def dijkstra(E,s,n):
  inf=float('inf')
  d=[inf for _ in range(n)]
  d[s]=0
  q=[]
  heappush(q,(d[s],s))
  while q:
    du, u1 = heappop(q)
    if d[u1]<du: continue
    for v1,weight in E.get(u1,[]):
      alt=du+weight
      if d[v1]>alt:
        d[v1]=alt
        heappush(q, (alt,v1))
  return d

c = []
c2 = []
for i in range(m):
  c.append([u[i]-1,v[i]-1,a[i]])
  c.append([v[i]-1,u[i]-1,a[i]])
  c2.append([u[i]-1,v[i]-1,b[i]])
  c2.append([v[i]-1,u[i]-1,b[i]])

p=dict()
for i,j,k in c: p[i]=p.get(i,[])+[(j,k)]

p2=dict()
for i,j,k in c2: p2[i]=p2.get(i,[])+[(j,k)]

d = dijkstra(p,s-1,n)
d2 = dijkstra(p2,t-1,n)

ans = [d[n-1]+d2[n-1]]
for i in range(1,n):
  ans.append(min(ans[i-1],d[n-1-i]+d2[n-1-i]))

for i in range(n):
  print(10**15-ans[n-1-i])

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

n,m,s,t = II()
u,v,a,b = Line(m)

from heapq import heappop, heappush
def dijkstra(E,s,n):
  inf=float('inf')
  d=[inf for _ in range(n)]
  d[s]=0
  q=[]
  heappush(q,(0,s))
  while q:
    du, u1 = heappop(q)
    if d[u1]<du: continue
    for v1,weight in E[u1].items():
      alt=du+weight
      if d[v1]>alt:
        d[v1]=alt
        heappush(q, (alt,v1))
  return d

p = [dict() for _ in range(n)]
p2 = [dict() for _ in range(n)]
for i in range(m):
  p[u[i]-1][v[i]-1] = a[i]
  p[v[i]-1][u[i]-1] = a[i]
  p2[u[i]-1][v[i]-1] = b[i]
  p2[v[i]-1][u[i]-1] = b[i]

d = dijkstra(p,s-1,n)
d2 = dijkstra(p2,t-1,n)

ans = [0]*n
ans[0] = d[n-1]+d2[n-1]
for i in range(1,n):
  ans[i] = min(ans[i-1],d[n-1-i]+d2[n-1-i])

for i in ans[::-1]:
  print(10**15-i)
### BUGGY CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
ave=[]
for i in range(N-K+1):
    tmp=0
    for j in range(K):
        tmp+=(p[i+j]+1)/2
    ave.append(tmp)
print(max(ave))

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
ave=[0]*(N-K+1)
tmp=0
for i in range(K):
    tmp+=(p[i]+1)/2
ave[0]=tmp
for i in range(1,N-K+1):
    ave[i]=ave[i-1]-(p[i-1]+1)/2 + (p[i+K-1]+1)/2
print(max(ave))
### BUGGY CODE ###

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

ans = 0
for i in range(N-1):
  for j in range(i, N):
    if A[i] + A[j] == j - i:
      ans += 1

print(ans)

### FIXED CODE ###

from collections import defaultdict

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

di = defaultdict(int)
dj = defaultdict(int)
for i in range(1, N+1):
  di[i + A[i-1]] += 1
  dj[i - A[i-1]] += 1

ans = 0
for key in di.keys():
  ans += dj[key] * di[key]

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

class LazySegmentTree:
    """
    Range Max Query
    Node must be positive.
    """

    def __init__(self, n, sentinel=0):
        self.n = 1 << (n + 1).bit_length()
        m = (self.n << 1) - 1
        self.data = [sentinel] * m
        self.lazy = [sentinel] * m
        self.flag = [False] * m
        self.sentinel = sentinel

    def _eval(self, i, l, r):
        if self.flag[i]:
            self.data[i] = max(self.data[i], self.lazy[i])
            if r - l > 1:
                li = (i << 1) + 1
                self.lazy[li] = max(self.lazy[li], self.lazy[i])
                self.lazy[li + 1] = max(self.lazy[li + 1], self.lazy[i])
                self.flag[li] = self.flag[li + 1] = True
            self.flag[i] = False

    def update(self, a, b, x, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return

        self._eval(i, l, r)

        if a <= l and r <= b:
            self.lazy[i] = x
            self.flag[i] = True
            self._eval(i, l, r)
        else:
            m = (l + r) // 2
            li = (i << 1) + 1
            self.update(a, b, x, li, l, m)
            self.update(a, b, x, li + 1, m, r)
            self.data[i] = max(self.data[li:li + 2])

    def get_max(self, a, b, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return self.sentinel

        self._eval(i, l, r)

        if a <= l and r <= b:
            return self.data[i]

        m = (l + r) // 2
        li = (i << 1) + 1
        return max(self.get_max(a, b, li, l, m), self.get_max(a, b, li + 1, m, r))


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
srt = sorted((h, i) for i, h in enumerate(hhh))
lst = LazySegmentTree(n, 0)

for h, i in srt:
    lst.update(i, lst.n, lst.get_max(0, i) + aaa[i])
    # print(lst.data)
    # print(lst.lazy)
    # print(lst.flag)
print(lst.get_max(0, n))


### FIXED CODE ###

def solve(n, hhh, aaa):
    n2 = 1 << n.bit_length()
    offset = n2 - 1
    data = [0] * ((n2 << 1) - 1)

    def update(k, x):
        i = k + offset
        data[i] = max(data[i], x)
        while i:
            i = (i - 1) // 2
            data[i] = max(data[i], x)

    def get_max(k):
        i = k + offset
        ret = data[i]
        while i:
            if i % 2 == 0:
                ret = max(ret, data[i - 1])
            i = (i - 1) // 2
        return ret

    srt = sorted((h, i) for i, h in enumerate(hhh))
    for h, i in srt:
        update(i, get_max(i) + aaa[i])

    return data[0]


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, hhh, aaa))
### BUGGY CODE ###

n = int(input())
def is_prime(num):
    import math
    if num == 2:
        return True
    elif num <  3 or num % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True

if is_prime(n):
    print(n-1)
    exit()

ans = float('inf')
for i in range(n//2, 0, -1):
    if n%i == 0:
        ans = min(ans, (i-1)+(n//i-1))
print(ans)

### FIXED CODE ###

n = int(input())
def is_prime(num):
    import math
    if num == 2:
        return True
    elif num <  3 or num % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True

if is_prime(n):
    print(n-1)
    exit()

ans = float('inf')
for i in range(int(n**0.5), 0, -1):
    if n%i == 0:
        ans = min(ans, (i-1)+(n//i-1))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(300000) #上限上げないと引っかかる




n,q = map(int, input().split())
sco = [0]*(n+1)
G =[[] for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

for j in range(q):
    p,x = map(int, input().split())
    sco[p]+=x


#本体
seen = [False for _ in range(n+1)]
def dfs(G,V,score):
    global sco
    sco[V] +=score

    seen[V] = True
    for next_V in G[V]:
        if (seen[next_V]):
            continue
        dfs(G, next_V,sco[V])

#入力受け取り
#例
dfs(G,1,0)
print(*sco[1:])
#単にdfs(G,0)だと、木構造でないとき(頂点1つでない時)不正解


### FIXED CODE ###

import sys
sys.setrecursionlimit(300000) #上限上げないと引っかかる
n,q = map(int, sys.stdin.readline().rstrip().split())
sco = [0]*(n+1)
G =[[] for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int, sys.stdin.readline().rstrip().split())
    G[a].append(b)
    G[b].append(a)

for j in range(q):
    p,x = map(int, sys.stdin.readline().rstrip().split())
    sco[p]+=x


#本体
seen = [False for _ in range(n+1)]
def dfs(G,V,score):
    global sco
    sco[V] +=score

    seen[V] = True
    for next_V in G[V]:
        if (seen[next_V]):
            continue
        dfs(G, next_V,sco[V])

#入力受け取り
#例
dfs(G,1,0)
print(*sco[1:])
#単にdfs(G,0)だと、木構造でないとき(頂点1つでない時)不正解
### BUGGY CODE ###

s = input()
N = int(input())
Q = [input().split() for _ in range(N)]

for q in Q:
    if int(q[0]) == 1:
        s = s[::-1]
    elif int(q[1]) == 1:
        s = q[2] + s
    else:
        s = s + q[2]

print(s)


### FIXED CODE ###

s = input()
N = int(input())
Q = [input().split() for _ in range(N)]

head = ''
tail = ''
reverse = 0

for q in Q:
    if int(q[0]) == 1:
        reverse = 1 - reverse
    elif int(q[1]) == 1:
        if reverse:
            tail += q[2]
        else:
            head += q[2]
    else:
        if reverse:
            head += q[2]
        else:
            tail += q[2]

if reverse:
    print(tail[::-1] + s[::-1] + head)
else:
    print(head[::-1] + s + tail)
### BUGGY CODE ###

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

#参考: https://qiita.com/ophhdn/items/e6451ec5983939ecbc5b
def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans


def main():
    n,a,b  = map(int, input().split())
    #a,bの制約がなければ，2^n - 1通りだけ使える
    # 2^n ^ nCa - nCb
    mod = 10**9 +7
    
    mab = max(a, b)
    ncr = [1 for i in range(mab+1)]
    for i in range(mab+1):
        if i == 0:
            continue
        else:
            ncr[i] = ncr[i-1] * (n-i+1) // i % mod

    n2 = pow(2, n) 
    nca = ncr[a]
    ncb = ncr[b] 
    print((n2 - nca - ncb - 1) % mod )
    eprint(n2)
    eprint(nca)
    eprint(ncb)
    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def comb(n,r,mod):
    p,q=1,1
    for i in range(r):
        p=p*(n-i)%mod 
        q=q*(i+1)%mod 
    return p*pow(q,mod-2,mod)%mod

def main():
    n,a,b  = map(int, input().split())
    #a,bの制約がなければ，2^n - 1通りだけ使える
    # 2^n ^ nCa - nCb
    mod = 10**9 +7
    nca = comb(n,a,mod)
    ncb = comb(n,b,mod)

    print((pow(2,n,mod)-(nca+ncb)%mod) % mod-1)


    return

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

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
q = int(input())
l = [list(map(int, input().split())) for _ in range(q)]
dic = Counter(a)

for i in range(q):
    (b, c) = l[i] 
    num = dic[b]
    dic[b] = 0
    if dic[c] == 0:
        dic[c] = num
    else:
        dic[c] += num
    ans = 0
    for i, j in dic.items():
        ans += i*j
    print(ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
q = int(input())
l = [list(map(int, input().split())) for _ in range(q)]
dic = Counter(a)
S = sum(a)
for i in range(q):
    (b, c) = l[i] 
    num = dic[b]
    S -= b*num
    dic[b] = 0
    if dic[c] == 0:
        dic[c] = num
    else:
        dic[c] += num
    S += c*num
    print(S)
### BUGGY CODE ###

from operator import itemgetter

N = int(input())
X = [(int(x),ind) for ind,x in enumerate(input().split())]
X.sort(key=itemgetter(0))
B = [0]*N
for i in range(N):
    B[X[i][1]] = (X[:i]+X[i+1:])[(N-2)//2]
for i in B:
    print(i[0])


### FIXED CODE ###

N = int(input())
X = [int(x) for x in input().split()]
B = sorted(X)
for i in X:
    if(i<B[N//2]):
        print(B[N//2])
    else:
        print(B[N//2-1])
### BUGGY CODE ###

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

for i in range(n):
    if i % 2 != n % 2:
        b.insert(0,a[i])
    else:
        b.append(a[i])

string = ""
for _ in b:
    string = string + str(_) + " "

print(string[:-1])


### FIXED CODE ###

import sys
from collections import deque

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

for i in range(n):
    if i % 2 != n % 2:
        b.appendleft(a[i])
    else:
        b.append(a[i])

for _ in b:
    sys.stdout.write(str(_) + " ")
sys.stdout.write("\n")
### BUGGY CODE ###

from copy import deepcopy
INF=10**18
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
c=deepcopy(a)
for k in range(n):
  for i in range(n):
    for j in range(n):
      c[i][j]=min(c[i][j],c[i][k]+c[k][j])
for i in range(n):
  for j in range(n):
    if a[i][j]!=c[i][j]:
      print(-1)
      exit()
ans=0
for i in range(n):
  for j in range(n):
    for k in range(n):
      if k==j or k==i:continue
      if c[i][j]==c[i][k]+c[k][j]:break
    else:ans+=c[i][j]
print(ans//2)

### FIXED CODE ###

n=int(input())
dis=[list(map(int,input().split())) for _ in range(n)]
c=[[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
  for j in range(n):
    c[i][j]=min(dis[i][k]+dis[k][j] for k in range(n))
for i in range(n):
  for j in range(n):
    if c[i][j]!=dis[i][j]:
      print(-1)
      exit()
for i in range(n):
  for j in range(n):
    for k in range(n):
      if i==k or j==k:continue
      if dis[i][j]==dis[i][k]+dis[k][j]:c[i][j]=0
print(sum(sum(c[i]) for i in range(n))//2)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
count = []
for i in range(1,n):
  if s[i-1] == 'A' and s[i] == 'C':
    count.append(i-1)

for _ in range(q):
  ans = 0
  l,r = map(int, input().split())
  for j in range(len(count)):
    if l-1 <= count[j] and count[j] < r-1:
      ans += 1
  print(ans)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
count = [0]*n
for i in range(1,n):
    count[i]+=count[i-1]
    if s[i-1:i+1] == 'AC':
        count[i]+=1
for _ in range(q):
    l,r = map(int,input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

def main():
	n, *a = map(int, open(0).read().split())
	mod = 10 ** 9 + 7
	l = [[x >> k & 1 for k in range(61)] for x in a]
	ll = [sum(t) for t in zip(*l)]
	ans = sum(s * (n - s) * (1 << i) % mod for i, s in enumerate(ll))
	print(ans % mod)

if __name__ == "__main__":
	main()

### FIXED CODE ###

n, *a = map(int, open(0).read().split())
ans = 0
mod = 10 ** 9 + 7
for k in range(61):
	m = 1 << k
	c = 0
	for x in a:
		if m & x:
			c += 1
	ans += (c) * (n - c) * m
	ans %= mod
print(ans)
### BUGGY CODE ###

from collections import Counter
N=int(input())
X=list(map(int,input().split()))
Y=sorted(X)
for i in range(N):
    for j in range(N):
        if X[i]==Y[j]:
            if j<N//2:
                print(Y[N//2])
                break
            else:
                print(Y[N//2-1])
                break

### FIXED CODE ###

from collections import Counter
N=int(input())
X=list(map(int,input().split()))
Y=sorted(X)
a=Y[N//2]
b=Y[N//2-1]
for i in X:
    if i<=b:
        print(a)
    else:
        print(b)
### BUGGY CODE ###

N = int(input())

S = []
for i in range(N):
    S.append(sorted(list(input())))

cnt = 0
for i in range(N-1):
    for j in range(i+1,N):
        if S[i] == S[j]:
            cnt += 1
            
print(cnt)
        

### FIXED CODE ###

N = int(input())

S = []
cnt = 0
c = {}

for i in range(N):
    s = "".join(sorted(list(input())))
    if s not in c.keys():
        c[s] = 1
    else:
        c[s] += 1
        cnt += c[s]-1
        
    S.append(s)

print(cnt)
### BUGGY CODE ###

n = int(input())
nums = [int(input()) for _ in range(n)]

count = 0
selected = [False for _ in range(n)]
for i in range(n):
    if not selected[i]:
        selected[i] = True
        count += 1

        m = nums[i]
        for j in range(i + 1, n):
            if not selected[j]:
                num = nums[j]
                if num > m:
                    m = num
                    selected[j] = True
print(count)

### FIXED CODE ###

import bisect
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n = ri()
ls = ris(n)
ls = [-x for x in ls]

dp = [float('inf')] * n
for x in ls:
    dp[bisect.bisect_right(dp, x)] = x
print(bisect.bisect_left(dp, float('inf')))