Harryxun/stf_run huggingface dataset:
n=int(input())

s=input()
X=int(s,2)

one_cnt=s.count("1")

modp=[0]*n
modm=[0]*n

for i in range(n):
    modp[i]=(pow(2,(n-i-1),one_cnt+1)*int(s[i]))%(one_cnt+1)
    modm[i]=(pow(2,(n-i-1),one_cnt-1)*int(s[i]))%(one_cnt-1)

ans=[]
memo_one=[0]*(n+10)

#print(modp,modm)

for i in range(n):
    cnt=0
    mod=0

    for j in range(n):
        if s[i]=="1":
            if one_cnt-1==0:
                ans.append(0)
                break

            if i!=j:
                mod=(mod+modm[j])%(one_cnt-1)
        else:
            if i!=j:
                mod=(mod+modp[j])%(one_cnt+1)
            else:
                mod=(mod+2**(n-i-1))%(one_cnt+1)
    cnt=1

   # print(i,mod)

    if mod==0:
        ans.append(cnt)
    else:
        while 1:
            cnt+=1
            if memo_one[mod]!=0:
                mod=mod%(memo_one[mod])
            else:
                tmp=(bin(mod).count("1"))
                memo_one[mod]=tmp
                mod=mod%(tmp)
            if mod==0:
                ans.append(cnt)
                break
            #print(mod,one_cnt,s[i],cnt)




#print(ans_memo)

for item in ans:
    print(item)
            









### FIXED CODE ###

def popcount(x):
    return bin(x).count("1")

n=int(input())
s=input()
X=int(s,2)

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if one_cnt-1!=0 else 0

for i in range(n):
    if s[i]=="1":
        if one_cnt-1==0:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    #print(i,"num",num)
    cnt=1
    while num!=0:
        num=num%popcount(num)
        cnt+=1
    print(cnt)
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def fac(n):
    if n== 1 or n == 0:
        return 1
    return n * fac(n-1)

def comb(n, k):
    return fac(n)/(fac(k) * fac(n-k))

def solve():
    n, a, b = f()
    v = f()
    
    v = sorted(v, reverse = True)

    c = v[a-1]

    cnt1 = 0
    total = 0

    for i in range(n):
        if v[i] == c:
            total += 1
            if i < a:
                cnt1 += 1


    print("{:.7f}".format(sum(v[0:a])/a))
    if v[0] == c:
        ans = 0
        for i in range(a, b+1):
            ans += comb(total, i)
        print(ans)
    else:
        print(int(comb(total, cnt1)))

solve()


### FIXED CODE ###

import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def fac(n):
    if n== 1 or n == 0:
        return 1
    return n * fac(n-1)

def comb(n, k):
    if k >n:
        return 0
    return fac(n)/(fac(k) * fac(n-k))

def solve():
    n, a, b = f()
    v = f()
    
    v = sorted(v, reverse = True)

    c = v[a-1]

    cnt1 = 0
    total = 0

    for i in range(n):
        if v[i] == c:
            total += 1
            if i < a:
                cnt1 += 1


    print("{:.7f}".format(sum(v[0:a])/a))
    if v[0] == c:
        ans = 0
        for i in range(a, b+1):
            ans += comb(total, i)
        print(int(ans))
    else:
        print(int(comb(total, cnt1)))

solve()
import sys
sys.setrecursionlimit(5000)
n, k = map(int, input().split())
p_lis = list(map(int, input().split()))
def calc_ex(num):
    return (num - 1) * 0.5 + 1
cur_num = 0
for i in range(k):
    cur_num += p_lis[i]
max_nums = cur_num
max_nums_i = i
for i in range(len(p_lis) - k):
    cur_num -= p_lis[i]
    cur_num += p_lis[i + k]
    if max_nums < cur_num:
        max_nums = cur_num
        max_nums_i = i + 1
res = 0
for i in range(max_nums_i, max_nums_i + k):
    res += calc_ex(p_lis[i])
print(res)    

### FIXED CODE ###

n, k = map(int, input().split())
p_lis = list(map(int, input().split()))
def calc_ex(num):
    return (num - 1) * 0.5 + 1
cur_num = 0
for i in range(k):
    cur_num += p_lis[i]
max_nums = cur_num
max_nums_i = 0
for i in range(len(p_lis) - k):
    cur_num -= p_lis[i]
    cur_num += p_lis[i + k]
    if max_nums < cur_num:
        max_nums = cur_num
        max_nums_i = i + 1
res = 0
for i in range(max_nums_i, max_nums_i + k):
    res += calc_ex(p_lis[i])
print(res)
N = int(input())
A = list(map(int, input().split()))
ans =1;
iszero = False

if 0 in A:
  iszero = True

for i in range(N):
  if(iszero):
    ans = 0
    break
    
  ans *= A[i]
  
  if(ans>10**18):
    ans = -1

print(ans

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans =1;
iszero = False

if 0 in A:
  iszero = True
for i in range(N):
  if(iszero):
    ans = 0
    break
  ans *= A[i] 
  if ans>10**18:
    ans = -1
    break

print(ans)
n = input()
a = list(map(int, input().split())
while True:
	sum(a)
	if sum % 2:
		break
	for num in a:
		num = num / 2
	i += 1
print(i)

### FIXED CODE ###

from time import sleep
n = input()
A = list(map(int, input().split()))
i = 0
while True:
    if len([a for a in A if a % 2]) > 0:
        break
    A = list(map(lambda x: x/2, A))
    i+=1
print(i)
a, b = map(int, input().split())

A = a + b
if A < 10:
  print(A):
else:
  print("error")

### FIXED CODE ###

a, b = map(int, input().split())
if a + b < 10:
  print(a + b)
else:
  print("error")
W,H,x,y,r = map(int, raw_input().split(' '))
if W <= x+r and H <= y+r:
print "Yes"
else:
print "No"

### FIXED CODE ###

W,H,x,y,r = map(int, input().split())
if r <= x <= W-r and r <= y <= H-r:
    print ('Yes')
else:
    print ('No')
N = int(input())
seat = [0]*100000
for i in range(N):
    a,b = map(int,list(input().split()))
    for j in range(a,b+1):
        seat[j] = 1
print(sum(seat))


### FIXED CODE ###

N = int(input())
seat = [0]*100000
for i in range(N):
    a,b = map(int,list(input().split()))
    for j in range(a,b+1):
        seat[j-1] = 1
print(sum(seat))
A=int(input())
B=int(input())
C=int(input())
X=int(input())

count=0

for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if 500*i+100*j+50*k==X:
                count+=1
            else:
                pass
print(count)
                



### FIXED CODE ###

X=int(input())
A=int(input())
B=int(input())

X=X-A

while True:
    X=X-B
    if X-B<0:
        break
    else:
        pass
print(X)
a = []
for _ in range(4):
    a.append(int(input))

print(min(min(a[0],a[1]), min(a[2],a[3])))


### FIXED CODE ###

a = []
for _ in range(4):
    a.append(int(input()))

print(min(a[0],a[1])+ min(a[2],a[3]))
da = list(map(int,input().split()))

k = [[0 for i in range(2)]for j in range(10001)]

i = 0

su = 0

j = 0

while da[0] != 0 and da[1] != 0:

	i = 0
	su = 0
	j = 0
	for i in range(da[0]):
		k[i][0],k[i][1] = list(map(int,input().split()))
		su += k[i][0] * k[i][1]

	k = sorted(k,key = lambda x: x[1],reverse = True)
	while da[1] != 0 and j != i+1:
		if da[1] >= k[j][0]:
			su -= k[j][0] * k[j][1]
			da[1] -= k[j][0]
			j += 1
		elif da[1] > 0 and da[1] < k[j][0] and j != i + 1:
			su -= da[1] * k[j][1]
			da[1] = 0
        else:
            j += 1

	print(su)

	da = list(map(int,input().split()))
	if da[0] == 0 and da[1] == 0:
		break
	k = [[0 for i in range(2)]for j in range(10001)]



### FIXED CODE ###

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

k = [[0 for i in range(2)]for j in range(10001)]
i = 0
su = 0
j = 0

while da[0] + da[1] != 0:
	i = 0
	su = 0
	j = 0
	for i in range(da[0]):
		k[i][0],k[i][1] = map(int,input().split())


	k = sorted(k,key = lambda x: x[1],reverse = True)

	while j != i + 1:
		if da[1] > k[j][0]:
			da[1] -= k[j][0]
			j += 1
		elif da[1] <= k[j][0] and da[1] > 0:
			su += (k[j][0] - da[1]) * k[j][1]
			da[1] = 0
			j += 1
		else:
			su += k[j][0] * k[j][1]
			j += 1

	print(su)

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

	k = [[0 for i in range(2)]for j in range(10001)]
def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    if x % y == 0:
        return y
    else:
        while x % y != 0:
            z = x % y
            x = y
            y = z
        else:
            return z


def lcm(m, n):
    return int(m * n / gcd(m, n))


n = int(input())
# つまり全t[i]で割り切れる値を出せということ
# 最小公倍数を出せばよい
sum = int(input())
for i in range(1, n):
    t = int(input())
    # print("sum:{} t:{} lcm:{}".format(sum, t, lcm(sum, t)))
    sum = lcm(sum, t)
print(sum)
"""
# 入力 : 自然数     ex) 12
# 出力 : 約数リスト ex) [2, 2, 3]
def factorization(n):
    R = int(n)
    s = 0
    L = []
    div = 2
    first = True
    while s == 0:
        for i in range(div, R + 1):
            if n % i == 0:
                n = n / i
                if i == div and not first:
                    alreadyExist = True
                else:
                    alreadyExist = False
                first = False
                div = i
                if n == 1:
                    s = 1
                if alreadyExist:
                    L[-1][1] += 1
                else:
                    L.append([i, 1])
                break
    return L


n = int(input())
t = [0 for i in range(n)]
fact = []
for i in range(n):
    # print(i)
    t[i] = int(input())
    if i == 0:
        fact = factorization(t[i])
    else:
        tmpFact = factorization(t[i])
        for _tmpFact in tmpFact:
            for _fact in fact:
                if _fact[0] == _tmpFact[0]:
                    _fact[1] = max(_fact[1], _tmpFact[1])
                    break
                elif _fact[0] == fact[-1][0]:
                    fact.append(_tmpFact)
# つまり全t[i]で割り切れる値を出せということ
# 最小公倍数を出せばよい
sum = 1
for _fact in fact:
    sum *= _fact[0]**_fact[1]
print(sum)
"""


### FIXED CODE ###

def gcd(a, b):
    while b > 0:
        tmp = a
        a = b
        b = tmp % b
    return a


def lcm(a, b):
    tmp = gcd(a, b)
    return (a//tmp) * b


n = int(input())
t = [0 for i in range(n)]
for i in range(n):
    t[i] = int(input())
t = sorted(t)
_sum = t[0]
for i in range(1, n):
    # print("sum:{} t:{} lcm:{}".format(sum, t, lcm(sum, t)))
    _sum = lcm(_sum, t[i])
    # print(sum)
print(_sum)
n = input()
l = [int(e) for e in input().split(" ")]
res = 1
for e in l:
    res = res*e
if res > 1e+18:
    print("-1")
else:
    print(res)

### FIXED CODE ###

a,b = [int(e) for e in input().split(" ")]
print(a*b)
n, q = map(int, input().split())

childs = [[] for _ in range(n+1)]
parent = [-1 if i == 1 else None for i in range(n+1)]
nodes_in_level = [[] for _ in range(n+1)]
level_of_node = [0 if i == 1 else None for i in range(n+1)]

level_of_node[0].append(1)

for _ in range(n-1):
  a, b = map(int, input().split())
  childs[a].append(b)
  parent[b] = a
  level_of_node[b] = level_of_node[a] + 1
  nodes_in_level[level_of_node[b]].append(b)

ans = 0
nodes_under_level = [0 for i in range(n+1)]
for i in list(range(n))[::-1]:
  nodes_under_level[i] = nodes_under_level[i+1] + len(nodes_in_level[i])

for _ in range(q):
  p, x = map(int, input().split())
  ans += nodes_under_level[level_of_node[p]] * x
  
print(ans)
  

### FIXED CODE ###

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

childs = [[] for _ in range(n+1)]
parent = [-1 if i == 1 else None for i in range(n+1)]
plus = [0 for i in range(n+1)]

for _ in range(n-1):
  a, b = map(int, input().split())
  childs[a].append(b)
  parent[b] = a

for _ in range(q):
  p, x = map(int, input().split())
  plus[p] += x
  
nodes = [1]
while nodes:
  node = nodes.pop()
  if childs[node]:
    for cn in childs[node]:
      plus[cn] += plus[node]
      nodes.append(cn)

print(' '.join([str(num) for num in plus[1:n+1]]))
from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[0 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0] = 1
for l,r,t in lrx:
  if t != 1:
    for g in range(l):
      for b in range(max(1,g)):
        for x,y,z in permutations((r,g,b)):
          dp[x][y][z] = -1
  if t != 2:
    for g in range(l,r):
      for b in range(l):
        for x,y,z in permutations((r,g,b)):
          dp[x][y][z] = -1
  if t != 3:
    for g in range(l,r):
      for b in range(l,g):
        for x,y,z in permutations((r,g,b)):
          dp[x][y][z] = -1

for r in range(n):
  for g in range(r):
    for b in range(max(1,g)):
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[mx+1][g][b] >= 0:
        dp[mx+1][g][b] += v
        dp[mx+1][g][b] %= mod
      if dp[r][mx+1][b] >= 0:
        dp[r][mx+1][b] += v
        dp[r][mx+1][b] %= mod
      if dp[r][g][mx+1] >= 0:
        dp[r][g][mx+1] += v
        dp[r][g][mx+1] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    for x,y,z in permutations((n,i,j)):
      if dp[x][y][z] >= 0:
        ans += dp[x][y][z]
        ans %= mod
print(ans*6%mod)
"""

### FIXED CODE ###

from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[0 for b in range(max(1,g))] for g in range(max(1,r))] for r in range(n+1)]
dp[0][0][0] = 1
for l,r,t in lrx:
  if t != 1:
    for g in range(l):
      for b in range(max(1,g)):
        dp[r][g][b] = -1
  if t != 2:
    for g in range(l,r):
      for b in range(l):
        dp[r][g][b] = -1
  if t != 3:
    for g in range(l,r):
      for b in range(l,g):
        dp[r][g][b] = -1

for r in range(n):
  for g in range(max(1,r)):
    for b in range(max(1,g)):
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
      if dp[r+1][r][b] >= 0:
        dp[r+1][r][b] += v
        dp[r+1][r][b] %= mod
      if dp[r+1][r][g] >= 0:
        dp[r+1][r][g] += v
        dp[r+1][r][g] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    if dp[n][i][j] >= 0:
      ans += dp[n][i][j]
      ans %= mod
print(ans%mod)
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int,input().split()))
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        x,y=map(int1,input().split())
        edge[x].append(y)
        edge[y].append(x)
    stack=[(0,1)]
    dp=[INF]*N
    dp[0]=0
    used=[False]*N
    ans=[0]*N
    while stack:
        v,l=stack.pop()
        used[v]=True
        dp[l:]=[INF]*(N-l)
        dp[bisect_right(dp,a[v]-1,hi=l)]=a[v]
        ans[v]=bisect_left(dp,INF,hi=l+1)-1
        for nv in edge[v]:
            if not used[nv]:
                stack.append((nv,l+1))
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int,input().split()))
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        x,y=map(int1,input().split())
        edge[x].append(y)
        edge[y].append(x)
    stack=[(0,1)]
    used=[False]*N
    ans=[0]*N
    dp=[INF]*(N+1)
    dp[0]=0
    dpdp=[]
    prev_l=1
    def dfs(v,l):
        used[v]=True
        index=bisect_right(dp,a[v]-1,hi=l)
        dpdp=(index,dp[index])
        dp[index]=a[v]
        ans[v]=bisect_left(dp,INF,hi=l+1)-1
        for nv in edge[v]:
            if not used[nv]:
                i,x=dfs(nv,l+1)
                dp[i]=x
        return dpdp
    dfs(0,1)
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()
import sympy

n = int(input())
x = sympy.divisors(n)

if len(x)%2 == 0:
    print(x[len(x)//2]+x[(len(x)//2)-1]-2)
else:
    print((x[(len(x)//2)]*2)-2)


### FIXED CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())
x = make_divisors(n)

if len(x)%2 == 0:
    print(x[len(x)//2]+x[(len(x)//2)-1]-2)
else:
    print((x[(len(x)//2)]*2)-2)
n = int(input())
p = [int(input()) for _ in range(n)]
q = [0] * (n+1)

for i in range(n):
    q[p[i]] = i
maxl = 1
cnt = 1
last = p[0]
for i in range(1, n):
    if q[i+1] > q[i]:
        cnt += 1
    else:
        maxl = max(maxl, cnt)
        cnt = 1

print(n - maxl)


### FIXED CODE ###

a, b, c, k = map(int, input().split())
res = b - a
if k % 2 ==0:
    res = a - b

if res > 10 ** 18:
    print('Unfair')
else:
    print(res)
import sys
input = sys.stdin.readline

n=int(input())
xs=input()
xk=list(map(int,list(xs)))
xj=xk.count(1)

x=int(xs,2)

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

for i in range(n-1,-1,-1):
    xi=x^(1<<i)
    pxi=xj
    if xk[n-1-i]==0:
        pxi=pxi+1
    else:
        pxi=pxi-1
    if xi==0:
        print(0)
    else:
        xi=xi%pxi
        if xi==0:
            print(1)
        else:
            icnt=1
            while xi>0:
                icnt+=1
                xi=xi%popcount(xi)
            print(icnt)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)
import itertools
from collections import defaultdict
H,W,N=map(int, raw_input().split())

A=[ [None for i in range(W+1) ] for j in range(H+1)]
for i in range(N):
	a,b=map(int, raw_input().split())
	A[a][b]=1

d=[-1,0,1]
D=list(itertools.product(d,d))

l=defaultdict(lambda: 0)

for x in range(2,H):
	for y in range(2,W):
		cnt=0
		for i,j in D:
			#print x+i,y+j,A[x+i][y+j]
			if A[x+i][y+j]==1:
				cnt+=1
		l[cnt]+=1


for i in range(10):
	print l[i]


### FIXED CODE ###

import itertools
from collections import defaultdict
from collections import Counter
H,W,N=map(int, raw_input().split())

d=[-1,0,1]
D=list(itertools.product(d,d))

A=defaultdict(lambda: 0)
for i in range(N):
	a,b=map(int, raw_input().split())
	for dx,dy in D:
		cx=a+dx
		cy=b+dy
		if cx>=2 and cx<=H-1 and cy>=2 and cy<=W-1:
			A[(cx,cy)]+=1

C=Counter(A.values())


for i in range(10):
	if i==0:
		print (H-2)*(W-2)-sum(C.values())
	else:
		print C[i]
import sys
input = sys.stdin.readline

x,n=map(int,input().split())
p=list(map(int,input().split()))

num=[i for i in range(1,101)]
for i in p:
    num[i-1]=0

num.sort()
while True:
    if num[0]!=0:
        break
    num.pop(0)
# print(num)

min=1000
for i in num:
    if min>abs(x-i):
        min=abs(x-i)
        ans=i
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

x,n=map(int,input().split())
p=list(map(int,input().split()))

# num=[i for i in range(1,101)]
# for i in p:
#     num[i-1]=-1

# num.append(0)
# num.append(101)
# num.sort()
# while True:
#     if num[0]!=-1:
#         break
#     num.pop(0)
# print(num)

# min=1000
# for i in num:
#     if min>abs(x-i):
#         min=abs(x-i)
#         ans=i
# print(ans)

i=0
while True:
    if not x-i in p :
        print(x-i)
        break
    elif not x+i in p:
        print(x+i)
        break
    i+=1

# num=[]
# for i in range(101):
#     num.append(x-i)
#     num.append(x+i)
import bisect
n = int(input())
l = sorted(list(map(int, input().split())))

dic = {}
ans = 0
for i in range(n-1):
  for j in range(i+1, n):
    tmp = l[i] + l[j]
    
    index2 = dic.get(tmp, -1)
    
    if index2 == -1
      index2 = bisect.bisect_left(l, tmp)
      dic[tmp] = index2
      
    index1 = dic.get(l[j], -1)
    if index == -1:
      index1 = bisect.bisect_left(l, l[j])
      dic[l[j]] = index1     
    
    if l[i] == l[j]:
      d = index2 - index1 - 2
    else:
      d = index2 - index1 - 1
    
    ans += max(d,0)
    
print(ans)

### FIXED CODE ###

import bisect as bs
n = int(input())
l = sorted(list(map(int,input().split())))

count = 0
for i in range(n):
  for j in range(i+1,n):
    index = bs.bisect_left(l,l[i]+l[j])
    count += index - j - 1
    
print(count)
num = map(int, input().split())
seki = num[0] * num[1]
if seki % 2 == 0:
    print(Even)
else:
    print(Odd)


### FIXED CODE ###

num1, num2 = map(int, input().split())
seki = num1 * num2
if seki % 2 == 0:
    print("Even")
else:
    print("Odd")
n = int(input())
l = [int(x) for x in input().split()]
sort(l)

print(n,l)

### FIXED CODE ###

n = int(input())
l = [int(x) for x in input().split()]

ans = 100000000000
for i in range(1,n):
  ans1 = sum(l[:i])
  ans2 = sum(l[i:])
  diff = abs(ans1 - ans2)
  if diff < ans:
    ans = diff
    
print(ans)
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
flag=0
if v<=w:
    if (a>=b):
        if (a-b)/(w-v)<=t:
            flag=1
elif (a==b):
    flag=1
elif (b-a)<0:
    pass
elif t==0:
    pass
elif (b-a)/(v-w)<=t:
    flag=1
if flag==1:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
flag=0
ky=abs(a-b)
if b==a:
    flag=1
elif w>=v:
    pass
elif abs((b-a)/(v-w))<=t:
    flag=1
if flag==1:
    print('YES')
else:
    print('NO')
import numpy as np
n=int(input())
a=list(map(int,input().split()))

#連続する重複を除外
arr=np.array(a)
diff=np.diff(arr,prepend=0)
aa=arr[np.nonzero(diff)]
#print(diff,aa)

aaa=aa.tolist()
point=[]
cnt=1

if len(aaa)<=2:
    print(1)
else:
    for i in range(len(aaa)-2):
        if (aaa[i+1]-aaa[i])*(aaa[i+2]-aaa[i+1])<0:
            cnt+=1
            point.append(i)
    
    if len(point)>1:
        for i in range(1,len(point)):
            if point[i]-1==point[i-1]:
                point[i]-=1
                cnt-=1
    print(cnt)

### FIXED CODE ###

import numpy as np
n=int(input())
a=list(map(int,input().split()))
b=a.copy()
b.insert(0,0)

#連続する重複を除外
arr=np.array(b)
diff=np.diff(arr)
arr2=np.array(a)
aa=arr2[np.nonzero(diff)]

aaa=aa.tolist()
point=[]
cnt=1
if len(aaa)<=2:
    print(1)
else:
    for i in range(len(aaa)-2):
        if (aaa[i+1]-aaa[i])*(aaa[i+2]-aaa[i+1])<0:
            cnt+=1
            point.append(i)
    
    if len(point)>1:
        for i in range(1,len(point)):
            if point[i]-1==point[i-1]:
                point[i]-=1
                cnt-=1
    print(cnt)