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

n=int(input())
a=list(map(int,input().split()))
gk=sum(a)
me=[0]
usr=[]
kgk=0
for i in range(n-1):
    kgk+=a[i]
    me.append(kgk)
    usr.append(gk-kgk)
usr.append(0)

ans=0
for i in range(n):
    for j in range(n-i):
        if gk-me[i]-usr[n-1-j]==0:
            ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
gk=[0]
kgk=0
for i in range(n):
    kgk+=a[i]
    gk.append(kgk)
gk.sort()
a=gk[0]
db=0
ans=0
for i in range(1,n+1):
    b=gk[i]
    if(a==b):
        db+=1
    else:
        a=b
        p=0
        for i in range(db+1):
           p+=i
        ans+=p
        db=0
p=0
for i in range(db+1):
    p+=i
ans+=p
print(ans)
### BUGGY CODE ###

n = input()
s = 0
while n > 0:
	n -= 1
	a = input()
	count = 0
	for i in range(1, int(a**0.5)+1):
		count += (a%i==0)
	if count == 1:
		s += 1
	#if sum(map(lambda x: a%x==0, range(1, int(a**0.5)+1))) == 1:
	#	s += 1
print s

		

### FIXED CODE ###

n = input()
s = 0
while n > 0:
	n -= 1
	a = input()
	if a == 1:
		pass
	elif a == 2:
		s += 1
	elif (a%2 == 1):
		for i in xrange(3, (int(a**0.5)+1), 2):
			if a%i==0:
				break	
		else:
			s += 1		
print s
### BUGGY CODE ###

n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    M=(m-1)*m*(2*m-1)//3
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+2*d*m*(m-1)+(m-d)*m*(m-1)-M
            ans=ans%INF
else:
    (n,m)=(m,n)
    M=(m-1)*m*(2*m-1)//3
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+2*d*m*(m-1)+(m-d)*m*(m-1)-M
            ans=ans%INF
import math
ans=(math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2)))*ans
ans=ans%INF
print(ans)


### FIXED CODE ###

n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    M=(m-1)*m*(2*m-1)//3
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+(m+d)*m*(m-1)-M
            ans=ans%INF
else:
    (n,m)=(m,n)
    M=(m-1)*m*(2*m-1)//3
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+(m+d)*m*(m-1)-M
            ans=ans%INF
import math
ans=(math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2)))*ans
ans=ans%INF
print(ans)
### BUGGY CODE ###

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

for _ in range(M):
  m = max(A)
  A[A.index(m)] = m // 2

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x:-x, A))

heapq.heapify(A)

for _ in range(M):
  a = -heapq.heappop(A)
  heapq.heappush(A, -(a//2))

print(-sum(A))
### BUGGY CODE ###

K = int(input())  #スペース抜きの複数行,１文字ずつ
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

A = []
A.append((K-1)*3)
A.append(((K-1)**2)*3)
A.append(1)
#print(A)
for i in range(2, K+1):
    for j in range(2, K+1):
        for k in range(2, K + 1):
#            if i != 1 and j != 1 and k != 1:
                #print(i, j, k)
                #print(gcd_list([i, j, k]))
                A.append(gcd_list([i, j, k]))

#print(A)
print(sum(A))

### FIXED CODE ###

K = int(input())  #スペース抜きの複数行,１文字ずつ
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

A = []
for i in range(1, K + 1):
    for j in range(i, K+1):
        for k in range(j, K + 1):
            if i == j and j == k and k == i:
                #print(i,j,k)
                A.append(gcd_list([i, j, k]))
            elif i != j and j != k and k != i:
                A.append(gcd_list([i, j, k])*6)
            else:
                #print(i,j,k)
                A.append(gcd_list([i, j, k])*3)           

print(sum(A))
### BUGGY CODE ###

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    S = 1
    for x in A:
        S *= x
    start = time.time()

    def factorization(n):
        ret = set()
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp % i == 0:
                cnt = 0
                while temp % i == 0:
                    cnt += 1
                    temp //= i
                ret.add(i)

        if temp != 1:
            ret.add(temp)

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret

    flag = True
    s = factorization(A[0])
    for x in A[1:]:
        tmp = 0
        now = time.time()
        if now - start > 2000:
            break
        for y in s:
            if x % y == 0:
                flag = False
                break
        if flag:
            s |= factorization(x)
            continue
        else:
            break

    if flag:
        print("pairwise coprime")
    else:
        g = A[0]
        for i, x in enumerate(A[::-1]):
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    M = max(A)
    X = [i for i in range(M+1)]
    S = [True for i in range(M+1)]
    S[0] = False
    S[1] = False

    for i in range(1, M+1):
        if S[i]:
            for j in range(i, M+1, i):
                if S[j]:
                    S[j] = False
                    X[j] = i
    flag = True
    s = set()
    ls = 0
    for x in A:
        tmp = set()
        while(X[x] != 1):
            tmp.add(X[x])
            x //= X[x]
        l = len(tmp)
        s |= tmp
        if len(s) == ls + l:
            ls += l
            continue
        else:
            flag = False
            break

    if flag:
        print("pairwise coprime")
    else:
        for x in A[1:]:
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()
### BUGGY CODE ###

x, y = map(int, input().split())
if x == y:
  print(-1)
else:
  now = x
  k = 1
  M = pow(10, 18)
  while now <= M:
    now = k * now
    if now % y != 0:
      break
  print(now)

### FIXED CODE ###

x, y = map(int, input().split())
if x == y or x % y == 0:
  print(-1)
else:
  now = x
  k = 1
  M = pow(10, 18)
  while now <= M:
    now = k * now
    if now % y != 0:
      break
    k += 1
  print(now)
### BUGGY CODE ###

import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, m = inintm()

t = []

for _ in range(m):
    a, b = inintm()
    if a == 1:
        if b in t:
            print("POSSIBLE")
            exit()
        t.append(b)
    elif b == n:
        if a in t:
            print("POSSIBLE")
            exit()
        t.append(a)

print("IMPOSSIBLE")


### FIXED CODE ###

import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, m = inintm()

t = [0]*(n+1)

for _ in range(m):
    a, b = inintm()
    if a == 1:
        if t[b] == 1:
            print("POSSIBLE")
            exit()
        t[b] = 1
    elif b == n:
        if t[a] == 1:
            print("POSSIBLE")
            exit()
        t[a] = 1

print("IMPOSSIBLE")
### BUGGY CODE ###

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

for i in range(1, n+1):
    alist.append(str(a.index(i)+1))

print(" ".join(alist))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
alist = [0]*n

for i in range(n):
    alist[a[i]-1] = str(i+1)

print(" ".join(alist))
### BUGGY CODE ###

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

a=[sum(A[:n]) for n in range(N+1)]
b=[sum(B[:m]) for m in range(M+1)]
num=0
bmax=M+1
for n in range(N+1):
    if a[n]>K:
        break
    for m in reversed(range(bmax)):
        if b[m]<=K-a[n]:
            num=max(num,n+m)
            bmax=m+1
            break
print(num)


### FIXED CODE ###

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

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

num=0
bmax=M+1
for n in range(N+1):
    if a[n]>K:
        break
    for m in reversed(range(bmax)):
        if b[m]<=K-a[n]:
            num=max(num,n+m)
            bmax=m+1
            break
print(num)
### BUGGY CODE ###

def get_(i):
    zero_len = 6-len(str(i))
    return '0'*zero_len+str(i)

N,M = list(map(int,input().split()))
N_list=[[] for n in range(N)]
M_list=[]

for m in range(M):
    P,Y=list(map(int,input().split()))
    N_list[P-1].append(Y)
    M_list.append([P,Y])
    
for n in N_list:
    n.sort()
    
for m in M_list:
    p=get_(m[0])
    
    i=N_list[m[0]-1].index(m[1])+1
    i=get_(i)
    
    print(p+i)

### FIXED CODE ###

def get_(i):
    zero_len = 6-len(str(i))
    return '0'*zero_len+str(i)

def get_idx(n,L):
    if len(L)<100:
        left=0
        right=len(L)
    else:    
        left=0
        right=len(L)

        i=0
        while i < 50:
            half=int((left+right)/2)
            if n <= L[half]:
                right = half
            else:
                left = half
            i+=1
        
    if left >= 1:
        left -= 1
        
    for i in range(left,right+1):
        if L[i]==n:
            return i

N,M = list(map(int,input().split()))
N_list=[[] for n in range(N)]
M_list=[]

for m in range(M):
    P,Y=list(map(int,input().split()))
    N_list[P-1].append(Y)
    M_list.append([P,Y])
    
for n in N_list:
    n.sort()
    
for m in M_list:
    p=get_(m[0])
    
    i=get_idx(m[1],N_list[m[0]-1])+1
    i=get_(i)
    
    print(p+i)
### BUGGY CODE ###

n,m,d = map(int, input().split())
if d ==0:
  print((n*n**(m-2)*(m-1))/n**m)
else:
  a =(n-d)*2*n**(m-2)*(m-1)
  print(a/n**m)

### FIXED CODE ###

n,m,d = map(int, input().split())
if d ==0:
  print(n*(m-1)/n**2)
else:
  print((n-d)*2*(m-1)/n**2)
### BUGGY CODE ###

import sys
imput=sys.stdin.readline
n,m=map(int,input().split())
l=[int(input()) for i in range(m)]
#print(l)
dp=[0]*(n+1)
dp[0]=1
if 1 not in l:
    dp[1]=1
else:dp[1]=0 
for i in range(2,n+1):
    if i in l:
        dp[i]=0
    else:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1]%(10**9+7))

### FIXED CODE ###

n,m=map(int,input().split())
a=[-1]
for i in range(m):
    s=int(input())
    a.append(s)  
a.append(n+1)
if 1 in a:
    a=a[1:]
if n-1 in a:
    a=a[:-1]
b=[]
for i in range(len(a)-1):
    b.append(a[i+1]-a[i]-2)
l=[1,1,2]
for i in range(3,n+1):
    l.append(l[i-2]+l[i-1])
ans=1
#print(a,b,l)
for i in range(len(b)):
    if b[i]<0:
        print(0)
        break
    else:
        ans*=l[b[i]]%1000000007
else:
    print(ans%1000000007)
### BUGGY CODE ###

N=int(input())
a=[int(input()) for i in range(N)]
ans=0
b=1
while(1):
    ans+=1
    b=a[b-1]
    if b==1:
        ans=-1
        break
    if b==2:break
print(ans)

### FIXED CODE ###

N=int(input())
a=[int(input()) for i in range(N)]
j=[0]*N
ans=0
b=1
while(1):
    ans+=1
    b=a[b-1]
    j[b-1]+=1
    if j[b-1]==2:
        ans=-1
        break
    if b==2:break
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
li=list(map(int, input().split()))
max=0
for i in range(n-k+1):
  tmp=0
  for j in range(k):
    tmp+=(li[i+j]+1)/2
  if max <= tmp:
    max=tmp
print(max)

### FIXED CODE ###

n,k=map(int,input().split())
li=list(map(int, input().split()))
tmp=0
for i in range(k):
  tmp+=li[i]

max=tmp
for i in range(1,n-k+1):
  tmp=tmp-li[i-1]+li[i+k-1]
  if max<=tmp:
    max=tmp
print((max+k)/2)
### BUGGY CODE ###

N = int(input())

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

import numpy as np

A_array = np.array(A_list)

A_max_list = list()
for i in range(len(A_array)):
    max_value = np.max(A_array[:i+1])
    A_max_list.append(max_value)
    
A_max_array = np.array(A_max_list)   

print(np.sum(A_max_array - A_array))


### FIXED CODE ###

N = int(input())

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

import numpy as np

B_list = A_list.copy()

for i in range(1, len(A_list)):
    if A_list[i] < A_list[i-1]:
        A_list[i] = A_list[i-1]
        
A_array = np.array(A_list)
B_array = np.array(B_list)

print(np.sum(A_array - B_array))
### BUGGY CODE ###

from operator import itemgetter
import heapq

N = int(input())
xy = [list(map(int,input().split())) + [i] for i in range(N)]

xroot = [[] for _ in range(N+1)]
yroot = [[] for _ in range(N+1)]

xlist = sorted(xy, key=itemgetter(0)) # [x, y, ID]
ylist = sorted(xy, key=itemgetter(1))
for i in range(N-1):
  x, hoge, xID = xlist[i]
  nextx, hoge, nextxID = xlist[i + 1]
  costx = abs(x - nextx)
  xroot[xID].append([costx, nextxID])
  xroot[nextxID].append([costx, xID])

  hoge, y, yID = ylist[i]
  hoge, nexty, nextyID = ylist[i + 1]
  costy = abs(y - nexty)
  yroot[yID].append([costy, nextyID])
  yroot[nextyID].append([costy, yID])
#print(xroot) # [cost, rootID]
#print(yroot)

hpop = heapq.heappop
hpush = heapq.heappush
data = [] # [Val, ID]

visited = [False]*(N+1)
hpush(data, [0, 0])
ans = 0
while data:
  val, num = hpop(data)
  if visited[num] == False:
    visited[num] = True
    #print(val, num)
    ans += val
    for i in xroot[num]:
      hpush(data, i)
    for j in yroot[num]:
      hpush(data, j)
print(ans)

### FIXED CODE ###

import sys
from operator import itemgetter
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    rnk[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if (rnk[x]<rnk[y]):
    par[x]=y
  else:
    par[y]=x
    if(rnk[x]==rnk[y]):
      rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N = I()
xlist = []
ylist = []

par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
init(N)

for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])
xlist.sort(key=itemgetter(0))
ylist.sort(key=itemgetter(0))

node = []
for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  
  node.append([nextx - x, xID, nextxID])
  node.append([nexty - y, yID, nextyID])
node.sort(key=itemgetter(0), reverse=True)

ans = 0
while node:
  val, i, j = node.pop()
  if same(i, j):
    continue
  else:
    unite(i, j)
    ans += val
print(ans)
### BUGGY CODE ###

K,S = map(int,input().split())
ans = 0
for a in range(K+1):
    for b in range(K+1):
        for c in range(K+1):
            if S == a + b + c:
                ans += 1
print(ans)

### FIXED CODE ###

K,S = map(int,input().split())
ans = 0
for a in range(K+1):
    for b in range(K+1):
        c = S - a - b
        if 0 <= c and c <= K:
            ans += 1
print(ans)
### BUGGY CODE ###

def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))

    for i in range(m):
        a.sort(reverse=True)
        a[0] = a[0] // 2
    print(sum(a))
if __name__=='__main__':
    main()


### FIXED CODE ###

import heapq
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    for i,aa in enumerate(a):
        a[i] = -1 * aa
    heapq.heapify(a)
    for i in range(m):
        tmp = heapq.heappop(a) * (-1) // 2
        heapq.heappush(a,tmp * (-1))
    print(sum(a) * (-1))
if __name__=='__main__':
    main()
### BUGGY CODE ###

import bisect

ans = 0
N = int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort()
B.sort()
C.sort()

for i in range(len(A)):
    #Aを1つ決めた時、BがA以下の値
    A_miman = bisect.bisect_right(B,A[i])
    for j in range(A_miman,N):
        #Bを1つ決めた時、CがB以上の値
        over_B = N - bisect.bisect_right(C, B[j])
        ans += over_B


print(ans)

### FIXED CODE ###

import bisect

ans = 0
N = int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort()
B.sort()
C.sort()


#A<B<Cの組み合わせの数が答え
for i in range(N):
    #Bを1つ決めた時、AがB未満の場合の総数
    B_miman = bisect.bisect_left(A,B[i])
    #Bを1つ決めた時、CがB以上の場合の総数
    B_ijou = N - bisect.bisect_right(C, B[i])

    ans+= B_miman*B_ijou

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

N, K = list(map(int, input().split()))
ab = []
for i in range(N-1):
    ab.append(list(map(int, input().split())))

ki = []

for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = 0

for i in range(N-1):
    ki[ab[i][0] - 1]["eda"]+=1
    ki[ab[i][1] - 1]["eda"]+=1

def P(m ,n):
    if m <= 0 or n <= 0:
        return 1
    else:
        num = 1
        for i in range(n):
            num *= m-i
        return num



total_num = K
if ki[0]["eda"] != 0:
    total_num *= P(K-1, ki[0]["eda"])
    for i in range(1, N):
        if K-1 < ki[i]["eda"]:
            total_num = 0
            break
        total_num *= P(K-2, ki[i]["eda"]-1)
        total_num = total_num % 1000000007
        if total_num == 0:
            break

print(total_num)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

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

dp_memo = [[float("inf")]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    dp_memo[i][i] = 0

def dp(i,j):
    if dp_memo[i][j] < float("inf"):
        return dp_memo[i][j]
    elif (j-i)%2 == N%2: # 先手番
        tmp = max(a[i] + dp(i+1, j), a[j-1] + dp(i,j-1))
        dp_memo[i][j] = tmp
        return tmp
    else: # 後手番
        tmp = min(-a[i] + dp(i+1, j), -a[j-1] + dp(i,j-1))
        dp_memo[i][j] = tmp
        return tmp

print(dp(0, N))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

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

dp = [[float("inf")]*(N+1) for _ in range(N+1)]

for shift_i in range(N+1):
    for i in range(N+1):
        if i+shift_i >= N+1:
            continue
        if shift_i == 0:
            dp[i][i] = 0
        elif ((i+shift_i)-i)%2 == N%2: # 先手番
            dp[i][(i+shift_i)] = max(a[i] + dp[i+1][(i+shift_i)], a[(i+shift_i)-1] + dp[i][(i+shift_i)-1])
        else:
            dp[i][(i+shift_i)] = min(-a[i] + dp[i+1][(i+shift_i)], -a[(i+shift_i)-1] + dp[i][(i+shift_i)-1])

print(dp[0][N])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
for a in A:
    ans *= a
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
A.sort()
for a in A:
    if a == 0:
        print(0)
        exit()
    ans *= a
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
L = []
R = []
D = []
G = [[] for _ in range(N+1)]
for _ in range(M):
    tmpl, tmpr, tmpd = map(int, input().split())
    # if tmpl > tmpr:
    #    tmpl, tmpr = tmpr, tmpl
    #    tmpd *= -1
    L.append(tmpl)
    R.append(tmpr)
    D.append(tmpd)
    G[tmpl].append((tmpr, tmpd))
    G[tmpr].append((tmpl, -tmpd))

field = [None] * (N+1)


def dfs(i):
    q = deque()
    q.append(i)
    field[i] = 0
    used = [False]*(N+1)
    used[i] = True
    while q:
        tmp = q.pop()
        for elem in G[tmp]:
            if used[elem[0]]:
                if field[elem[0]] is not None:
                    if field[elem[0]] != field[tmp]+elem[1]:
                        return False
                continue
            q.append(elem[0])
            if field[elem[0]] == None:
                field[elem[0]] = field[tmp]+elem[1]
                used[elem[0]] = True
            else:
                if field[elem[0]] != field[tmp]+elem[1]:
                    return False

    return True


for i in range(1, N+1):
    if field[i] == None:
        if not dfs(i):
            print('No')
            exit()
print('Yes')


### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
#L = []
#R = []
#D = []
G = [[] for _ in range(N+1)]
for _ in range(M):
    tmpl, tmpr, tmpd = map(int, input().split())
    # L.append(tmpl)
    # R.append(tmpr)
    # D.append(tmpd)
    G[tmpl].append((tmpr, tmpd))
    G[tmpr].append((tmpl, -tmpd))

field = [None] * (N+1)


def dfs(i):
    q = deque()
    q.append(i)
    field[i] = 0
    #used = [False]*(N+1)
    #used[i] = True
    while q:
        tmp = q.pop()
        for elem in G[tmp]:
            if field[elem[0]] is not None:
                if field[elem[0]] != field[tmp]+elem[1]:
                    return False
                continue
            else:
                q.append(elem[0])
                field[elem[0]] = field[tmp]+elem[1]

            # if used[elem[0]]:
            #    if field[elem[0]] is not None:
            #        if field[elem[0]] != field[tmp]+elem[1]:
            #            return False
            #    continue
            # q.append(elem[0])
            # if field[elem[0]] == None:
            #    field[elem[0]] = field[tmp]+elem[1]
            #    used[elem[0]] = True
            # else:
            #    if field[elem[0]] != field[tmp]+elem[1]:
            #        return False

    return True


for i in range(1, N+1):
    if field[i] == None:
        if not dfs(i):
            print('No')
            exit()
print('Yes')
### BUGGY CODE ###

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

while True:
    a.sort(reverse = True)
    x = True
    for i in range(n):
        if a[i] % 2 == 0:
            if x:
                a[i] = a[i] // 2
                x = False
    if x:
        print(t)
        exit(0)
    else:
        t += 1

### FIXED CODE ###

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

for i in range(n):
    while a[i] % 2 == 0:
        a[i] = a[i] // 2
        t += 1
        
print(t)
### BUGGY CODE ###

import bisect

N=int(input())
A=[int(input()) for i in range(N)]
count=0
while A:

    nowN=A[-1]
    A.pop()
    count+=1
    i=len(A)-1
    while i>=0:
        if A[i]<nowN:
            nowN=A[i]
            A.pop(i)
        i-=1


    #print(count,A)
print(count)


### FIXED CODE ###

import bisect
import collections

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=collections.deque([])
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if lst:
            lst.pop()
        else:
            count+=1
        continue
    idx=bisect.bisect_left(lst,A[i])-1
    #print(idx,lst,A[i])
    if idx<0:
        lst.appendleft(A[i])
        count+=1
    else:
        lst[idx]=A[i]

print(count)