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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



f=lambda:map(int,input().split())
N,M=f()
uf=UnionFind(N+1)
for _ in range(M):
    a,b=f()
    uf.union(a,b)
    
print(max([len(i) for i in list(uf.all_group_members().values())]))

### FIXED CODE ###

# D
from collections import deque
from bisect import bisect_left as bl

f=lambda:map(int,input().split())
N,M=f()
D=[[] for _ in [0]*(N+1)]
F=[0]*(N+1)
F[0]=1
for _ in range(M):
    a,b=f()
    D[a].append(b)
    D[b].append(a)

q=deque()
res=0


while bl(F,1):
    index=bl(F,1)-1
    q.append(index)
    tmp=0
    while q:
        k=q.pop()
        if F[k]!=1:
            tmp+=1
            F[k]=1
            for d in list(set(D[k])):
                if F[d]!=1:
                    q.append(d)
            D[k]=0
    res=max(res,tmp)

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

import math
honsu,hp=map(int , input().split())
huru=[]
nageru=[]
for i in range(honsu):
  a,b=input().split()
  huru+=[int(a)]
  nageru+=[int(b)]
cc=filter(lambda v:v>=max(huru) , nageru)
cou=0
for i in reversed(sorted(cc)):
  hp-=i
  cou+=1
  if hp<=0:
    break
if hp>0:
  cou+=math.ceil(hp/max(huru))
print(cou)

### FIXED CODE ###

from math import ceil
 
N, H = map(int, input().split())
a, b = [], []
 
for _ in range(N):
    a_i, b_i = map(int, input().split())
    a.append(a_i)
    b.append(b_i)
 
max_a = max(a)
b = sorted(b, reverse=True)
ans = float('inf')
th_po = 0
 
for i in range(N):
    th_po += b[i]
    
    if H >= th_po:
        ans_cand = i + 1 + ceil((H - th_po) / max_a)
    else:
        ans_cand = i + 1
    
    ans = min([ans, ans_cand])
 
print(ans)
### BUGGY CODE ###


#アルゴリズムはあってるがLTE
N = int(input())
wordl = []

for i in range(N):
    w = input()
    wl = []
    for j in range(10):
        wl.append(w[j])
    wl.sort()
    w2 = ' '
    for p in range(10):
        w2 += wl[p]
    wordl.append(w2)
wordl.sort()
#print(wordl)

ans = 0
for k in range(N):
    for q in range(k+1,N):
        if wordl[k] == wordl[q]:
            ans += 1
        else:
            break

print(ans)


### FIXED CODE ###

N = int(input())
wordl = {}
ans = 0

for i in range(N):
    w = input()
    wl = []
    for j in range(10):
        wl.append(w[j])
    wl.sort()
    w2 = ' '
    for p in range(10):
        w2 += wl[p]
    if w2 in wordl:
        ans += wordl[w2]
        wordl[w2] += 1
    else:
        wordl[w2] = 1

print(ans)

'''
#アルゴリズムはあってるがLTE
N = int(input())
wordl = []

for i in range(N):
    w = input()
    wl = []
    for j in range(10):
        wl.append(w[j])
    wl.sort()
    w2 = ' '
    for p in range(10):
        w2 += wl[p]
    wordl.append(w2)
wordl.sort()
#print(wordl)

ans = 0
for k in range(N):
    for q in range(k+1,N):
        if wordl[k] == wordl[q]:
            ans += 1
        else:
            break

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

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in set(a):
    b.append(a.count(i))
b.sort()
ans = 0
for i in range(len(set(a)) - k):
    ans += b[i]
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
import collections
count_dict = collections.Counter(a)
# print(count_dict.most_common())
ans = 0
unique = count_dict.most_common()
for i in range(len(count_dict) - k):
    ans += unique[len(count_dict)-i-1][1]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
h = list(map(int,input().split()))
a,m = 0,0
for i in range(n-1):
  if m < n-i:
    for j in range(i+1,n):
      if h[j-1] >= h[j]:
        a += 1
        if j == n-1:
          m = max(m,a)
          a = 0
      else:
        i = i + a + 1
        m = max(m,a)
        a = 0
        break
print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
h = list(map(int,input().split()))

count,m = 0,0

for i in range(n-1):
  if h[i] >= h[i+1]:
    count += 1
  else:
    m = max(m,count)
    count = 0
m = max(m,count)
print(m)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

#f = open(sys.argv[1], "r")
#input = f.readline

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

b = {}
check = set()
i = 0
for h in range(H):
    for c in input().strip():
        if c == "#":
            b[i] = 1
            check.add(i)
        i += 1
t = 0

#import time
#t1 = time.time()

while len(b) != W*H:
    t += 1
    tb = set()
    #print(len(check))
    for i in check:
        if i-W >= 0:
            tb.add(i-W)
        if i%W > 0:
            tb.add(i-1)
        if i%W < W-1:
            tb.add(i+1)
        if i+W < H*W:
            tb.add(i+W)
    check.clear()
    for i in tb:
        if i not in b:
            check.add(i)
        b[i] = 1
print(t)

#print(time.time()-t1)


### FIXED CODE ###

import sys
input=sys.stdin.readline
H,W = map(int, input().split())

b = [[True]*(W+2)]
for _ in range(H):
    b.append([True] + [x == '#' for x in input().strip()] + [True])
b.append([True]*(W+2))

check = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            check.append((i,j))
t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

print(t-1)
### BUGGY CODE ###

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

    ans = sum(A)
    d = dict()
    for i, a in enumerate(A):
        if a not in d:
            d[a] = ()
        d[a] += (i,)

    for b, c in zip(B, C):
        if b not in d:
            print(ans)
            continue
        elif len(d[b]) == 0:
            print(ans)
            continue
        ans += len(d[b]) * (c-b)
        if c not in d:
            d[c] = ()
        d[c] = d[c] + d[b]
        d[b] = ()
        print(ans)

main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    B, C = [0]*Q, [0]*Q
    for i in range(Q):
        B[i], C[i] = map(int, input().split())

    ans = sum(A)
    d = dict()
    for i, a in enumerate(A):
        d[a] = d.get(a, 0) + 1

    for b, c in zip(B, C):
        if b not in d:
            print(ans)
            continue
        ans += d[b] * (c-b)
        if c not in d:
            d[c] = 0
        d[c] = d[c] + d[b]
        d[b] = 0
        print(ans)

main()
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque

class UnionFind():
        def __init__(self, n):
            self.parents = list(range(n))
    
        def find(self, x):
            if self.parents[x] == x:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]
    
        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
            if x != y:
                self.parents[y] = x

def main():
    N, M, K = map(int, input().split())
    friend_adj = [[] for _ in range(N)]
    block_adj = [[] for _ in range(N)]

    for _ in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        friend_adj[a].append(b)
        friend_adj[b].append(a)
    for _ in range(K):
        c, d = map(lambda x: int(x)-1, input().split())
        block_adj[c].append(d)
        block_adj[d].append(c)

    ans = [0] * N
    for i in range(N):
        uf = UnionFind(N)
        q = deque([i])
        visited = [-1] * N
        visited[i] = 0
        while q:
            now = q.popleft()
            for v in friend_adj[now]:
                if visited[v] < 0:
                    q.append(v)
                    visited[v] = 0
                    uf.union(now,v)
                    
        # print(uf.parents)
        ans[i] = uf.parents.count(i) - len(friend_adj[i]) - 1
        for b in block_adj[i]:
            if uf.parents[b] == i:
                ans[i] -= 1
    print(*ans)
    
    
    

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

class UnionFind():
        def __init__(self, n):
            self.parents = list(range(n))
            self.size = [1] * n
    
        def find(self, x):
            if self.parents[x] == x:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]
    
        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
            if x != y:
                if self.parents[x] > self.parents[y]:
                    x, y = y,x
                self.parents[y] = x
                self.size[x] += self.size[y]

def main():
    N, M, K = map(int, input().split())
    friend_adj = [[] for _ in range(N)]
    block_adj = [[] for _ in range(N)]
    uf = UnionFind(N)

    for _ in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        friend_adj[a].append(b)
        friend_adj[b].append(a)
        uf.union(a,b)
    for _ in range(K):
        c, d = map(lambda x: int(x)-1, input().split())
        if uf.find(c) == uf.find(d):
            friend_adj[c].append(d)
            friend_adj[d].append(c)

    ans = [uf.size[uf.find(i)]-1 for i in range(N)]

    for i in range(N):
        ans[i] -= len(friend_adj[i])        
        # for b in block_adj[i]:
        #     if uf.find(b) == uf.find(i):
        #         ans[i] -= 1
    print(*ans)
    
    
    

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

n,x,m = map(int,input().split())
a = []
a.append(0)
a.append(x)
for i in range(1,n):
  #tmp = (a[i]**2)%m
  tmp = (a[i]%m)*(a[i]%m)
  tmp = tmp%m
  a.append(tmp)
  if tmp==0:
    break
print(sum(a))


### FIXED CODE ###

n,x,m = map(int,input().split())
a = []
a.append(0)
a.append(x)
isBreak = False
for i in range(1,n):
  #tmp = (a[i]**2)%m
  tmp = (a[i]%m)*(a[i]%m)
  tmp = tmp%m
  if tmp==0:
    break
  if tmp in a:
    isBreak = True
    break
  a.append(tmp)
#print(a)
if isBreak:
  i = 1
  while a[i]!=tmp:
    i+=1
  kurikaeshi = len(a) - i
  goukei = sum(a[i:])
  #print(goukei)
  tmp=(n-(len(a)-1))
  #print(tmp//kurikaeshi)
  a.append(tmp//kurikaeshi * goukei)
  #print(a)
  tmp = tmp%kurikaeshi
  if tmp!=0:
    t = sum(a[i:i+tmp])
    a.append(t)
print(sum(a))
### BUGGY CODE ###

import itertools
N, C = map(int, input().split())
X = []
V = []
for n in range(N):
    x, v = map(int,input().split())
    X.append(x)
    V.append(v)
X_r = X[::-1]
V_r = V[::-1]
X = [0] + X
V = [0] + V
X_r = [0] + [C-x for x in X_r]
V_r = [0] + V_r

#cx = list(itertools.accumulate(X))
cv = list(itertools.accumulate(V))
#cxr = list(itertools.accumulate(X_r))
cvr = list(itertools.accumulate(V_r))

# print (X)
# print (X_r)
# print (cv)
# print (cvr)

# L = []
# for i in range(N+1):
#     L.append(cv[i]-X[i])
# R = []
# for i in range(N+1):
#     R.append(cvr[i]-X_r[i])

# print (L,R)
mx = 0
for l in range(N+1):
    m1 = -2*X[l]+cv[l]
    m2 = -2*X_r[l]+cvr[l]
    for r in range(N+1-l):
        #print (l,r)
        a = m1+cvr[r]-X_r[r]
        mx = max(mx,a)
        a = m2+cv[r]-X[r]
        mx = max(mx,a)
print (mx)

### FIXED CODE ###

import itertools
N, C = map(int, input().split())
X = []
V = []
for n in range(N):
    x, v = map(int,input().split())
    X.append(x)
    V.append(v)
Xr = X[::-1]
Vr = V[::-1]
Xl = [0] + X
Vl = [0] + V
Xr = [0] + [C-x for x in Xr] # 逆に回るのでCから引く
Vr = [0] + Vr

Vl = list(itertools.accumulate(Vl)) # xは累積した値なので、vも累積和に統一
Vr = list(itertools.accumulate(Vr))

def update_mx(ls):
    mx = 0
    for i in range(len(ls)):
        mx = max(mx, ls[i])
        ls[i] = mx
    return ls

def create(V,X,k):
    ls = []
    for n in range(N+1):
        ls.append(V[n]-k*X[n]) # 往復する場合はk=2
    return update_mx(ls)

L = create(Vl,Xl,1) # 最良の値[左端として許容される位置]（片道）
Lt = create(Vl,Xl,2) # 最良の値[左端として許容される位置]（往復）
R = create(Vr,Xr,1)
Rt = create(Vr,Xr,2)

ans = 0
for n in range(N+1):
    #print (n,N-n)
    ans = max(ans, Lt[n] + R[N-n])
    ans = max(ans, Rt[n] + L[N-n])
print (ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in a[:n-1]:
    j = sum(a[a.index(i)+1:])
    ans = (ans+i*j)%(10**9+7)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
r = sum(a)
for i in a[:n-1]:
    r = r - i
    ans = (ans+i*r)%(10**9+7)
print(ans)
### BUGGY CODE ###

from itertools import product
from string import digits

n = int(input())
s = input()

ret = 0
for perm in product(digits, repeat=3):
    i = 0
    for c in s:
        if c == perm[i]:
            i += 1
            if i == 3:
                break
    if i == 3:
        ret += 1

print(ret)


### FIXED CODE ###

def main():
    from collections import defaultdict

    n = int(input())
    s = input()

    d = defaultdict(bool)

    for c in s:
        for x in '0123456789':
            for y in '0123456789':
                if d[x + y]:
                    d[x + y + c] = True
        for x in '0123456789':
            if d[x]:
                d[x + c] = True
        d[c] = True

    print(sum(len(k) == 3 for k in d))


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

import collections
import sys
input = sys.stdin.readline
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

Q, K = map(int, input().split())
xy = [map(int, input().split()) for i in range(Q)]
k = [set() for i in range(N)]
g = [[-1]*N for i in range(N)]
for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c
    k[a-1].add(b-1)
    k[b-1].add(a-1)
c = [-1]*N
reached = [0]*N
c[K-1] = 0
q = collections.deque([K])
reached[K-1] = 1
while(len(q) > 0):
    x = q.popleft()

    for y in k[x-1]:
        if not reached[y]:
            q.append(y+1)
            c[y] = c[x-1]+g[x-1][y]
            reached[y] = 1

for x, y in xy:
    print(c[x-1] + c[y-1])


### FIXED CODE ###

N=int(input())
abc=[tuple(map(int,input().split())) for i in range(N-1)]
g=[set() for i in range(N)]
for a,b,c in abc:
  g[a-1].add((b-1,c))
  g[b-1].add((a-1,c))
memo=[-1]*N

Q,K=map(int,input().split())
import collections
q=collections.deque([(K-1,0)])
memo[K-1]=0
while(q):
  
  x,w = q.popleft()
  for a,b in g[x]:
    if memo[a]==-1:
      memo[a]=w+b
      q.append((a,w+b))
  
for i in range(Q):
  x,y=map(int,input().split())
  print(memo[x-1]+memo[y-1])
### BUGGY CODE ###

a, b = map(int, input().split())
result=a
for i in range(a+1, b+1):
    result^=i
print(result)


### FIXED CODE ###

a, b = map(int, input().split())
ta = list(map(int, list(bin(a))[:1:-1]))
tb = list(map(int, list(bin(b))[:1:-1]))
S  = [0]*40
E  = [0]*40
for i in range(len(ta)):
    S[i]=ta[i]
for i in range(len(tb)):
    E[i]=tb[i]
sum=0
for i in range(1,40):
    odd =0
    sodd=0
    eodd=0
    m0=a%(2**(i+1))
    M0=b%(2**(i+1))
    m1=a//(2**(i+1))
    M1=b//(2**(i+1))
    if m1==M1:
        if(S[i]==0 and E[i]==1 and b%2==0):
            odd = 1
        elif(S[i]==1 and (b-a)%2==0):
            odd = 1
    else:
        if(S[i]==0 and E[i]==1 and b%2==0):
            odd = 1
        elif(S[i]==1 and E[i]==0 and a%2==1):
            odd = 1
        elif(S[i]==1 and E[i]==1):
            sodd = 1 if (a%2==1) else 0
            modd = 1 if (b%2==0) else 0
            odd = sodd^modd
    sum+=(2**i)*odd

if((a//4)!=(b//4)):
    if(a%4>1 and (b%4==0 or b%4==3)):
        sum+=1
    elif(a%4<=1 and (b%4==1 or b%4==2)):
        sum+=1
else:
    if((b-a)==1 or ((b-a)==2 and a%2==0)):
        sum+=1

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

import math
N = int(input())
ans = 0

def division(n):
  cnt = 0
  for i in range(1, int(math.sqrt(n))+1):
    if n % i == 0:
      cnt += 1
  cnt *= 2
  if n % math.sqrt(n) == 0:
    cnt -= 1
  return cnt

for i in range(1, N+1):
  ans += i * division(i)
  
print(ans)

### FIXED CODE ###

N = int(input())

def num_divisors_table(n):
  table = [0] * (n + 1)
  for i in range(1, n + 1):
    for j in range(i, n + 1, i):
      table[j] += j
  return sum(table)

print(num_divisors_table(N))
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()
ans = 0
mod = [0]*P
if P==2 or P==5:
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
    print(ans)
else:
    un1 = 0
    un = 0
    for i in range(N-1, -1, -1):
        a = int(S[i])*10**un + un1
        un += 1
        un1 = a
        mod[a%P]+=1
    ans += mod[0]  
    for i in range(P):
        ans += mod[i]*(mod[i]-1)/2
    print(int(ans))

### FIXED CODE ###

N, P = map(int, input().split())
S = input()
ans = 0
mod = [0]*P
if P==2 or P==5:
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
    print(ans)
else:
    un1 = 0
    un = 0
    for i in range(N-1, -1, -1):
        #a =int(S[i])*10**un + un1
        a =int(S[i])*pow(10,un,P)+(un1)%P
        un += 1
        un1 = a
        mod[a%P]+=1
    ans += mod[0]  
    for i in range(P):
        ans += mod[i]*(mod[i]-1)/2
    print(int(ans))
### BUGGY CODE ###

import copy
import sys

n, q = map(int, sys.stdin.readline().split())

s = input()

letterPlace = {}

golemGroup = {}

for i, letter in enumerate(list(s)):
  if letter in letterPlace:
    letterPlace[letter].append(i)
  else:
    letterPlace[letter] = [i]
  golemGroup[i] = [1]

#print(golemGroup)

move = {
  "R" : 1,
  "L" : -1
}

for _ in range(q):
  spell = sys.stdin.readline().split()
  if spell[0] not in letterPlace:
    continue
  places = letterPlace[spell[0]]
  nextGroup = copy.copy(golemGroup)
  for place in places:
    if place == 0 and spell[1] == "L":
      del(nextGroup[place])
    elif place == n-1 and spell[1] == "R":
      del(nextGroup[place])
    else:
      if place not in golemGroup:
        continue
      if place + move[spell[1]] in golemGroup:
        nextGroup[place + move[spell[1]]] += golemGroup[place]
        del(nextGroup[place])
      else:
        nextGroup[place + move[spell[1]]] = golemGroup[place]
        del(nextGroup[place])
    golemGroup = copy.copy(nextGroup)
    #print(golemGroup)

out = 0
for v in golemGroup.values():
  out += len(v)

print(out)

### FIXED CODE ###

import copy
import sys

n, q = map(int, sys.stdin.readline().split())

s = input()

leftLimit = -1
rightLimit = n

spells =   spell = sys.stdin.readlines()
  
for spell in reversed(spells):
  target, direction = spell.split()
  if direction == "R" and target == s[rightLimit - 1]:
    rightLimit -= 1
    if rightLimit <= 0:
      break
  try:
    if direction == "R" and target == s[leftLimit]:
      if leftLimit != -1:
         leftLimit -= 1
  except Exception as e:
    pass
  if direction == "L" and target == s[leftLimit + 1]:
    leftLimit += 1
    if leftLimit >= n-1:
      break
  try:  
    if direction =="L" and target == s[rightLimit]:
      if rightLimit != n:
        rightLimit += 1
  except Exception as e:
    pass
  #print(target, direction, leftLimit, rightLimit)

print(max(rightLimit - leftLimit - 1 , 0))
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
    i = a.index(max(a))
    a[i] = a[i] // 2
print(sum(a))


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x) * -1, input().split()))
heapq.heapify(a)
for _ in range(m):
    tmp = (heapq.heappop(a) * (-1)) // 2
    heapq.heappush(a, -tmp)
print(sum(a) * -1)
### BUGGY CODE ###

num = int(input())

words = []
for _ in range(num):
    words.append(input())

words = tuple(words)

d = {}
for word in words:
    if word in d:
        d[word] += 1
    else:
        d[word] =1

max_k_list = (kv[0] for kv in d.items() if kv[1] == max(d.values()))
max_k_list = sorted(max_k_list)

print('\n'.join(max_k_list))

### FIXED CODE ###

import numpy as np

num = int(input())

words = []
for _ in range(num):
    words.append(input())

words = tuple(words)

d = {}
for word in words:
    if word in d:
        d[word] += 1
    else:
        d[word] =1


# keyをndarrayで取得
keys = np.array([a[0] for a in d.items()])

# valueをndarrayで取得
values = np.array([a[1] for a in d.items()])

# valueがmaxであるkeyを探してくる
keys_of_max_val = keys[values == values.max()]

keys_of_max_val.sort()

print('\n'.join(keys_of_max_val))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
if N % 2 == 0:
    
    for i in list(range(1, N, 2)):
        if A.count(i) == 2:
            ans += 1
        else:
            break
else:
    if A.count(0) == 1:
        
        for i in list(range(0, N, 2)):
            if 1 <= A.count(i) <=2:
                ans +=1
            else:
                break
    else:
        ans = 0

if ans != 0:
    if N%2 == 0:
        print((2**ans)%(10**9+7))
    else:
        print((2**(ans-1))%(10**9+7))
else:
    print(0)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
if N % 2 == 0:
    if len(A) != 2*len(set(A)):
        ans = 0
else:
    if A.count(0) == 1:
        A.remove(0)
        if len(A) != 2*len(set(A)):
            ans = 0
    else:
        ans = 0
if ans == 0:
    print(0)
else:
    print((2**(N//2))%(10**9+7))
### BUGGY CODE ###

from collections import deque
from functools import reduce

N, K = [int(n) for n in input().split()]
scores = [int(n) for n in input().split()]

d = deque(maxlen=200001)
for i, score in enumerate(scores, start=1):
    if i < K:
        d.append(score)
    elif i == K:
        d.append(score)
        pre_e = reduce(lambda x, y: x*y, d)
        d.popleft()
    else:
        d.append(score)
        e = reduce(lambda x, y: x*y, d)
        if e > pre_e:
            print('Yes')
        else:
            print('No')
        pre_e = e
        d.popleft()


### FIXED CODE ###

N, K = [int(n) for n in input().split()]
scores = [int(n) for n in input().split()]
min_pointer = 0
max_pointer = K
for i, score in enumerate(scores, start=1):
    if i > K:
        if scores[max_pointer] > scores[min_pointer]:
            print('Yes')
        else:
            print('No')
        min_pointer += 1
        max_pointer += 1
### BUGGY CODE ###

# setting
import numpy as np
from collections import deque

#------------------
# input part
n, m, q = map(int, input().split())

LR = np.array([[0 for _ in range(n)] for i in range(n)])
for i in range(m):
    l, r = map(int, input().split())
    LR[(l-1,r-1)] += 1

res = deque()
for i in range(q):
    p,q = list(map(int, input().split()))
    res.append(np.sum(LR[p-1:q, p-1:q]))
#------------------

#------------------
# print part
for r in res:
    print(r)
#------------------

### FIXED CODE ###

# setting
from itertools import accumulate

#------------------
n, m, q = map(int, input().split())

LR = [[0 for _ in range(n-i)] for i in range(n)]
for i in range(m):
    l, r = map(int, input().split())
    LR[l-1][r-l] += 1

for i in range(n-2, -1, -1):
    for j, acc in enumerate(accumulate(LR[i])):
        LR[i][j] = acc  + (0 if j == 0 else LR[i+1][j-1])

res = list()
for i in range(q):
    p,q = map(int, input().split())
    res.append(LR[p-1][q-p])

for r in res:
    print(r)