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

N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
#######################
# 開始
p_list = XY[:]

# y座標の圧縮
p_list = sorted(p_list, key=lambda x: x[1])
p_list = [ {'x': p[0], 'y': p[1], 'y_rank': i+1} for i, p in enumerate(p_list)]

# xでソート
p_list= sorted(p_list, key=lambda x: x['x'])

a = [] # 左下
b = [] # 左上
c = [] # 右下
d = [] # 右上

# a,bを求める
bit = Bit(N)
for i, p in enumerate(p_list):
    a.append(bit.sum(p['y_rank']))
    b.append(i-a[-1])
    bit.add(p['y_rank'], 1)

#print(p_list)
#print(a)
#print(b)

# c,dを求める
bit = Bit(N)
for i, p in enumerate(reversed(p_list)):
    c.append(bit.sum(p['y_rank']))
    d.append(i-c[-1])
    bit.add(p['y_rank'], 1)
c = c[::-1]
d = d[::-1]
#print(c)
#print(d)

# ある点が四角に含まれる場合の総数を求めるメソッド
def p_comb(a, b, c, d):
    a = pow(2, a) - 1
    b = pow(2, b) - 1
    c = pow(2, c) - 1
    d = pow(2, d) - 1
    
    # 中心だけ
    ret = 1
    # 一か所だけ(必ず中心点を入れる)
    ret += a + b + c + d
    # 対角線2か所(中心点はどちらでも)
    ret += (a*d + b*c)*2
    # 隣接2か所(必ず中心点を入れる)
    ret += (a*b+b*d+d*c+c*a)
    # 3か所(中心点はどちらでも)
    ret += (a*b*d+b*d*c+d*c*a+c*a*b)*2
    # 4か所
    ret += a*b*c*d*2
    return ret
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)   


### FIXED CODE ###

N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#######################
# 開始
from operator import itemgetter
def solve():
    p_list = XY[:]

    # y座標の圧縮
    p_list = sorted(p_list, key=itemgetter(1))
    p_list = [ (x, y, i+1) for i, (x, y) in enumerate(p_list)]

    # xでソート
    p_list= sorted(p_list)

    # ある点が四角に含まれる場合の総数を求めるメソッド
    power = [1] * N
    for i in range(1, N):
        power[i] = power[i-1] * 2 % 998244353

    # a,bを求める
    bit = Bit(N)
    ans = 0
    for i, (x, y, r) in enumerate(p_list):
        tmp = bit.sum(r)
        a = tmp
        b = i-tmp
        c = r-tmp-1
        d = (N-r+1)-(i-tmp)-1
        bit.add(r, 1)
        _a = power[a] - 1
        _b = power[b] - 1
        _c = power[c] - 1
        _d = power[d] - 1

        ret = (_a+1) * (_d+1) * _c * _b
        ret += (_b+1) * (_c+1) * _a * _d
        ret -= _a*_b*_c*_d
        ret += power[N-1]
        ans += ret % 998244353

    print(ans % 998244353)
    
solve()
### BUGGY CODE ###


N,H = map(int,input().split())

a = []
b = []
finish = 0

for i in range(1,N+1):
    elem1, elem2 = map(int,input().split())
    a.append(elem1)
    b.append(elem2)

#print(max(b))
sum = max(b)
b.remove(max(b))
count = 1
for elem in b:
    if elem > max(a):
        sum = sum + elem
    #print(sum)
        count += 1
        if sum > H:
            finish = 1
            break


#print(sum)
if finish == 0:
    dev = int(((H - sum)/(max(a))))
    count = count + dev
    sum = sum + dev * max(a)
    if sum < H:
        count += 1

print(count)


### FIXED CODE ###


N,H = map(int,input().split())

a = []
b = []
finish = 0

for i in range(1,N+1):
    elem1, elem2 = map(int,input().split())
    a.append(elem1)
    b.append(elem2)


b = sorted(b, key=int, reverse=True)

maxB = max(b)
maxA = max(a)
sum = maxB
b.remove(maxB)
count = 1
for elem in b:
    if elem > maxA and sum < H:
        sum = sum + elem
        count += 1
    if sum >= H:
        finish = 1
        break


#print(sum)
if finish == 0:
    dev = int((H - sum)/maxA)
    count = count + dev
    sum = sum + dev * maxA
    if sum < H:
        count += 1

print(count)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]

flag = True

while flag:
    for i in range(N-1):
        for j in range(i+1, N):
            if A[i] == A[j]:
                print('NO')     
                flag = False      
while flag:
    print('YES')

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]

if len(A) != len(set(A)):
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
c = [a.count(i) for i in range(1, n+1)]
for i in range(n):
  print(c[i])

### FIXED CODE ###

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

a,b=map(int,input().split())
c=0
while a>0 or b>0:
  if (a-2)>0 or (b-2)>0:
    a=a-2
    b=b-2
    c=c+1
print(c)  


### FIXED CODE ###

a,b=map(int,input().split())
c=0
d=a*(a-1)//2
e=b*(b-1)//2
while d>0:
  d=d-1
  c=c+1
while e>0:
  e=e-1
  c=c+1
print(c)
### BUGGY CODE ###

a = int(input())
ar = list(map(int,input().split(" ")))
b = 1
for r in ar:
  b *= r
if b > 10 ** 18:
    print(-1)
else:
    print(b)


### FIXED CODE ###

a = int(input())
ar = list(map(int,input().split(" ")))
if 0 in ar:
    print(0)
    exit()
b = 1
for r in ar:
    b *= r
    if b > 10 ** 18:
        print(-1)
        exit()
print(b)
### BUGGY CODE ###

m = {0: {1, 4}, 1: {0, 2, 5}, 2: {1, 3, 6}, 3: {2, 7},
     4: {0, 5, 8}, 5: {1, 4, 6, 9}, 6: {2, 5, 7, 10}, 7: {3, 6, 11},
     8: {4, 9, 12}, 9: {5, 8, 10, 13}, 10: {6, 9, 11, 14}, 11: {7, 10, 15},
     12: {8, 13}, 13: {9, 12, 14}, 14: {10, 13, 15}, 15: {11, 14}}
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
def solve():
    board = sum((list(map(int, input().split())) for _ in range(4)), [])
    zero = board.index(0)
    if board == GOAL:
        return 0
    def df_lower_search(limit, move, space, before):
        if move == limit:
            if board == GOAL:
                return True
        else:
            for i in m[space]:
                if i == before:
                    continue
                p = board[i]
                board[space] = p
                board[i] = 0
                if move + 1 <= limit:
                    if df_lower_search(limit, move + 1, i, space):
                        return True
                board[space] = 0
                board[i] = p
    for l in range(1, 46):
        if df_lower_search(l, 0, zero, None):
            return l
def MAIN():
    print(solve())
MAIN()



### FIXED CODE ###

from heapq import heappop, heappush
manhattan = tuple(tuple(abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)) for i in range(16))
movables = ((1, 4), (0, 2, 5), (1, 3, 6), (2, 7), (0, 5, 8), (1, 4, 6, 9), (2, 5, 7, 10), (3, 6, 11),
            (4, 9, 12), (5, 8, 10, 13), (6, 9, 11, 14), (7, 10, 15), (8, 13), (9, 12, 14), (10, 13, 15), (11, 14))
swap_mul = tuple(tuple((1 << mf) - (1 << mt) for mt in range(0, 64, 4)) for mf in range(0, 64, 4))
destination = 0xfedcba9876543210
i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1
estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)
queue = [(estimation_init, board_init, blank_init)]
visited = set()
while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))
### BUGGY CODE ###

import bisect
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = [- 1, P_id[N], N] 


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    a = A[j]
    l1 = A[j - 1]
    r1 = A[j + 1]
    if l1 != - 1:
        l2 = A[j - 2]
    else:
        l2 = l1
    if r1 != N:
        r2 = A[j + 2]
    else:
        r2 = r1
    
    if l1 == - 1:
        res += i*(a + 1)*(r2 - r1)
    elif r1 == N:
        res += i*(l1 - l2)*(N - a)
    else:
        res += i*((a - l1)*(r2 - r1) + (l1 - l2)*(r1 - a))
print(res)

### FIXED CODE ###

import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)
### BUGGY CODE ###

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

max_sum = 0

for i in range(n-k+1):
    max_sum = max(max_sum, sum(p[i:i+k]))

ans = (max_sum + k) / 2
print(ans)

### FIXED CODE ###

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

max_x = 0
idx = 0
x = 0

if n == k:
    print((sum(p) + k) / 2)
    exit()

for i in range(n-k):
    x += p[i+k] - p[i]
    if max_x < x:
        max_x = x
        idx = i+1

ans = (sum(p[idx:idx+k]) + k) / 2
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
n = int(input())

ans = 1

for i in range(n):
    ans *= i + 1

print(ans % 1000000007)


### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())

ans = 1

for i in range(n):
    ans *= i + 1
    ans %= 1000000007

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

import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
N = I()
for i in range(1, N+1):
    heihoukon = math.floor(math.sqrt(i))
    tmp = 0
    for x in range(1, heihoukon):
        for y in range(1, heihoukon):
            for z in range(1, heihoukon):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
                    tmp += 1
                if x**2 + y**2 + z**2 + x*y + y*z + z*x > i:
                    break
    print(tmp)

### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
N = I()
ans = [0 for _ in range(0, 10050)]
for i in range(1, 101):
    for j in range(1, 101):
        for k in range(1, 101):
            n = i*i + j*j + k*k + i*j + j*k + k*i
            if n < 10050:
                ans[n] += 1
            else:
                continue
for i in range(1, N +1):
    print(ans[i])
### BUGGY CODE ###

import re


N = int(input())
S = input()
ans = 0

passwords = [str(i).zfill(3) for i in range(1000)]
for pw in passwords:
    if re.search(re.compile('.*{0[0]}.*{0[1]}.*{0[2]}.*'.format(pw)), S):
        ans += 1

print(ans)



### FIXED CODE ###

N = int(input())
S = input()

passwords = [str(i).zfill(3) for i in range(1000)]
ans = 0

for pw in passwords:
    S_copy = S
    FLG = True
    for digit in pw:
        if digit not in S_copy:
            FLG = False
            break
        else:
            index = S_copy.find(digit)
            S_copy = S_copy[index+1:]
    if FLG:
        ans += 1

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

import numpy as np
n,s = [int(c) for c in input().split()]
a = [int(c) for c in input().split()]
# t[i][j] : 0<=r<...,<l=iについて和がsになるようなf(r,l)の和
# t = [[0]*(s+1) for _ in range(n)]
t = np.zeros((n, s+1), dtype="int64")
if a[0]<=s:
    t[0,a[0]] = 1
for i in range(n):
    t[i,0] = i+2
for i in range(1,n):
    for j in range(1,s+1):
        tt = t[i-1,j]
        if j-a[i]>=0:
            tt += t[i-1,j-a[i]]
        t[i,j] = tt
print(t[:,s].sum()%998244353)

### FIXED CODE ###



n, s = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [[None] * (s+1) for _ in range(n+1)]
M = 998244353


for j in range(s+1):
    dp[0][j] = 0
for i in range(n+1):
    dp[i][0] = i+1

for i in range(1,n+1):
    for j in range(1, s+1):
        dp[i][j] = dp[i-1][j]
        if j-a[i-1]>=0:
            dp[i][j] += dp[i-1][j-a[i-1]]
        dp[i][j] %= M
print(sum((dp[i][s] for i in range(n+1)))%M)
### BUGGY CODE ###

N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = []
for _m in range(M):
    path = input().strip().split(' ')
    path = int(path[0]), int(path[1])
    path = path if path[0] < path[1] else (path[1], path[0])
    if path not in paths:
        paths.append(path)
good_flags = [1 for _ in range(N)]

for p1, p2 in paths:
    if H[p1-1] > H[p2-1]:
        good_flags[p2-1] = 0
    elif H[p1-1] < H[p2-1]:
        good_flags[p1-1] = 0
    else:
        good_flags[p1-1] = 0
        good_flags[p2-1] = 0        

print(sum(good_flags))

### FIXED CODE ###

N, M = [ int(i) for i in input().strip().split(' ') ]
H    = [ int(i) for i in input().strip().split(' ') ]
paths = []
max_neighbor = [ 0 for _ in range(N)]

for _m in range(M):
    path = input().strip().split(' ')
    path = int(path[0]), int(path[1])
    max_neighbor[path[0]-1] = max(max_neighbor[path[0]-1], H[path[1]-1])
    max_neighbor[path[1]-1] = max(max_neighbor[path[1]-1], H[path[0]-1])
count = 0
for n in range(N):
    if max_neighbor[n] < H[n]:
        count += 1
print(count)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
for i in range(q):
  l,r = map(int,input().split())
  ss = s[l-1:r]
  print(ss.count('AC'))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int,input().split())
s = list(input())
check = [0]*n
const = 0
for i in range(n-1):
    check[i] = const
    if s[i] == 'A' and s[i+1] == 'C':
        check[i+1] = const + 1
        const += 1
        i += 1
check[-1] = const
for i in range(q):
    l,r = map(int,input().split())
    print(check[r-1]-check[l-1])
### BUGGY CODE ###

K, S = map(int, input().split())
number = 0
for x in range(K+1):
  for y in range(x, K+1):
    for z in range(y, K+1):
      if x + y + z == S:
        if x == y and x == z:
          number += 1
        elif x == y or y == z or z == y:
          number += 3
        else:
          number += 6
print(number)


### FIXED CODE ###

K, S = map(int, input().split())
number = 0
for x in range(K+1):
  for y in range(K+1):
    z = S - (x + y)
    if 0 <= z <= K:
      number += 1
print(number)
### BUGGY CODE ###

S = input()
N = len(S)
S = int(S)

map_ = [-1] * 2019
map_[0] = 0
ans = 0

for i in range(1, N + 1):
    temp = S % (10**i)
    map_[temp % 2019] += 1
    ans += map_[temp % 2019]

print(ans)


### FIXED CODE ###

S = input()
N = len(S)

map_ = [-1] * 2019
map_[0] = 0
ans = 0
now = 0
for i in range(0, N):
    now = (now + int(S[N - i - 1]) * pow(10, i, 2019)) % 2019
    map_[now] += 1
    ans += map_[now]

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

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n = I()
s = S()
sa = s[:n]
sb = s[n:][::-1]

A = defaultdict(int)
B = defaultdict(int)

for bit in range(1<<n):
    red_A = ""
    red_B = ""
    blue_A = ""
    blue_B = ""
    for i in range(n):
        if bit & 1<<i:
            red_A += sa[i]
            blue_B += sb[i]
        else:
            blue_A += sa[i]
            red_B += sb[i]
    A[(red_A, blue_A)] += 1
    B[(blue_B, red_B)] += 1

ans = 0
for key in A.keys():
    if key in B.keys():
        ans += A[key]*B[key]

print(ans)


### FIXED CODE ###

from collections import defaultdict
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def S(): return input()
# ----------------------------------------------------------- #

n = I()
s = S()
sa = s[:n]
sb = s[n:][::-1]

A = defaultdict(int)
B = defaultdict(int)

for bit in range(1<<n):
    red_A = []
    red_B = []
    blue_A = []
    blue_B = []
    for i in range(n):
        if bit & 1<<i:
            red_A.append(sa[i])
            blue_B.append(sb[i])
        else:
            blue_A.append(sa[i])
            red_B.append(sb[i])
    a_key = ''.join(red_A) + ',' + ''.join(blue_A)
    b_key = ''.join(blue_B) + ',' + ''.join(red_B)
    A[a_key] += 1
    B[b_key] += 1

ans = 0
for key in A.keys():
    if key in B:
        ans += A[key]*B[key]

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

n,m=map(int,input().split())
i=0
x=[]
while i!=n:
    a=list(map(int,input().split()))
    x.append(a)
    i=i+1
x.sort()
m_now=0
n_now=0
while m!=m_now:
    a=x[0]
    del x[0]
    if m>=m_now+a[1]:
        m_now=m_now+a[1]
        n_now=n_now+a[0]*a[1]
    else:
        while m!=m_now:
            m_now=m_now+1
            n_now=n_now+a[0]
print(n_now)

### FIXED CODE ###

n,m=map(int,input().split())
i=0
x=[]
while i!=n:
    a=list(map(int,input().split()))
    x.append(a)
    i=i+1
x.sort()
m_now=0
n_now=0
while m!=m_now:
    a=x[0]
    del x[0]
    if m>=m_now+a[1]:
        m_now=m_now+a[1]
        n_now=n_now+a[0]*a[1]
    else:
        n_now=n_now+a[0]*(m-m_now)
        m_now=m
print(n_now)
### BUGGY CODE ###

a, b = map(int,input().split())
answer = b

for i in range(a, b):
    answer = answer ^ i

print(answer)

### FIXED CODE ###

a, b = map(int, input().split())
ans = b
done = 0
for i in range(a, b+1):
    if i % 4 != 0:
        ans ^= i
    else:
        done = i
        break

for i in range(b-1, a, -1):
    if i % 4 != 3 and i >= done:
        ans ^= i
    else:
        break

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

import sys
input = sys.stdin.readline

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

    dp = [[[0 for k in range(N + 1)]for j in range(N + 1)]for i in range(N + 1)]


    one = A.count(1)
    two = A.count(2)
    three = A.count(3)

    for k in range(three + 1):
        for j in range(two + three + 1 - k):
            for i in range(one + two + three + 1 -k -j):
                if i == 0 and j == 0 and k == 0:
                    continue
                ret = N
                if i > 0:
                    ret += dp[i - 1][j][k] * i
                if j > 0:
                    ret += dp[i + 1][j - 1][k] * j 
                if k > 0:
                    ret += dp[i][j + 1][k -1] * k

                dp[i][j][k] = ret / (i + j + k)

    print(dp[one][two][three])

main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

    dp = [[[0.0 for k in range(N + 1)]for j in range(N + 1)]for i in range(N + 1)]


    one = A.count(1)
    two = A.count(2)
    three = A.count(3)

    for k in range(three + 1):
        for j in range(two + three + 1 - k):
            for i in range(one + two + three + 1 -k -j):
                if i == 0 and j == 0 and k == 0:
                    continue
                ret = N * 1.0
                if i > 0:
                    ret += dp[i - 1][j][k] * i
                if j > 0:
                    ret += dp[i + 1][j - 1][k] * j 
                if k > 0:
                    ret += dp[i][j + 1][k -1] * k

                dp[i][j][k] = ret / (i + j + k)

    print(dp[one][two][three])

main()
### BUGGY CODE ###

n = int(input())
l = sorted(list(map(int,input().split())))
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            a = l[i]
            b = l[j]
            c = l[k]
            if a<b+c and b<a+c and c<a+b:
                cnt+=1
            else:
                break
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
cnt = 0
l = sorted(l)
for i in range(n):
    for j in range(i+1,n):
        d = l[i]+ l[j]
        cnt +=bisect.bisect_left(l,d) - (j+1)
print(cnt)
### BUGGY CODE ###

s = input()
s = s.replace("dream", "D")
s = s.replace("erase", "E")
ok = True
i = 0
while i <= len(s)-1:
    if s[i] in ["D","E"]: 
        i += 1
        continue
    if i == 0:
        ok = False
        break
    if s[i] == "e":
        if i+1>len(s) or  s[i+1]!="r" or s[i-1] != "D":
            ok = False
            break
        i += 2
    elif s[i] == "r":
        if s[i-1] != "E":
            ok = False
            break
        i += 1
print("YES" if ok else "NO")

### FIXED CODE ###

s = input()
n = len(s)

ans = ""
i = 0
for _ in range(n):
    if i > n or ans == s: break
    if s[i:i+5] == "erase":
        i += 5
        ans += "erase"
        if s[i:i+1] == "r":
            i += 1
            ans += "r"
    elif s[i:i+5] == "dream":
        i += 5
        ans += "dream"
        if s[i:i+3] == "era": continue
        elif s[i:i+2] == "er":
            i += 2
            ans += "er"
print("YES" if ans == s else "NO")
### BUGGY CODE ###

N = int(input())
check = []
def my_index(l, x, default=False):
    return l.index(x) if x in l else default

for _ in range(N):
    A = int(input())
    if A not in check:
        check.append(A)
    else:
        del check[my_index(check,A)]
print(len(check))

### FIXED CODE ###

from collections import Counter
import sys

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

def main():
    N = int(input())
    A = [input() for _ in range(N)]
    common = Counter(A).most_common()
    ans = 0
    for i in common:
        if i[1] % 2 == 1:
            ans += 1
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import heapq
N, K  = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, N):
    compare = []
    heapq.heapify(compare)
    cnt = min(K, i)
    for j in range(cnt):
        heapq.heappush(compare, dp[i-j-1] + abs(h[i]-h[i-j-1]))
    dp[i] = heapq.heappop(compare)

print(dp[-1])


### FIXED CODE ###

import heapq
N, K  = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, N):
    compare = []
    heapq.heapify(compare)
    cnt = min(K, i)
    for j in range(cnt):
        heapq.heappush(compare, dp[i-j-1] + abs(h[i]-h[i-j-1]))
    dp[i] = heapq.heappop(compare)

print(dp[-1])