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

#!/usr/bin/env python3
import sys
import collections


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    As = LI()
    As.sort()
    As.reverse()
    ans = []
    ans.append(As.pop(0))
    N -= 1

    for i in range(len(As)):
        tmp = As.pop(0)
        ans.extend([tmp, tmp])

    print(sum(ans[:N]))


# oj t -c "pypy3 main.py"
# acc s main.py -- --guess-python-interpreter pypy
main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    As = LI()
    As.sort()
    As.reverse()
    As = collections.deque(As)
    ans = []
    tmp = As.popleft()
    ans.append(tmp)

    for i in range(len(As)):
        tmp = As.popleft()
        ans.extend([tmp, tmp])

    print(sum(ans[:N-1]))
    # print(ans)


# oj t -c "pypy3 main.py"
# acc s main.py -- --guess-python-interpreter pypy
main()
### BUGGY CODE ###

n=int(input())
a=[]
k=0
for i in range(n):
    s=input()
    if s not in a:
        k+=1
        a.append(s)
print(k)

### FIXED CODE ###

n=int(input())
a=[]

for i in range(n):
    a.append(input())
b=set(a)
print(len(b))
### BUGGY CODE ###

#!/usr/bin/env python3
import numpy as np
import itertools

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    H, W, K = list(map(int, input().split()))
    S = np.ndarray([H, W])
    answer = np.inf

    for h in range(H):
        row = list(map(int, list(input())))
        S[h, :] = row

    for n in range(H):
        for comb in itertools.combinations([h for h in range(1, H)], n):
            num_horizontal_cut = len(comb)
            if num_horizontal_cut == 0:
                sub_S = S.sum(axis=0)
            else:
                sub_S = np.zeros([num_horizontal_cut+1, W])
                head = 0

                c_prev = 0
                for i, c in enumerate(comb):
                    sub_S[i] = S[c_prev: c].sum(axis=0)
                    c_prev = c
                sub_S[num_horizontal_cut] = S[c_prev:].sum(axis=0)
                """
                for h in range(H):
                    if h in comb:
                        head += 1
                    sub_S[head, :] += S[h, :]
                """

            current_sum = np.zeros(num_horizontal_cut+1)
            num_cut = 0
            if np.any(sub_S > K):
                num_cut = np.inf
                continue
            for line in sub_S.T:
                if np.any(current_sum + line > K):
                    current_sum = np.zeros(num_horizontal_cut+1)
                    num_cut += 1
                current_sum += line

            if num_cut + num_horizontal_cut < answer:
                answer = num_cut + num_horizontal_cut
    print(answer)
    pass

if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, list(input()))) for _ in range(H)])
 
ans = float('inf')
for pattern in product([0, 1], repeat=H - 1):
    # スライスで横方向への割り方を表現する
    div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [10]
 
    # 横方向へ割った後、各ブロックについて縦方向にホワイトチョコの数を修正
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0))
 
    # 縦方向にすでにK個より多いホワイトチョコが含まれている場合はどうにもならない
    if [r for r in rows if np.any(r > K)]:
        continue
 
    # 縦方向に貪欲に割っていく
    rows = [r.tolist() for r in rows]
    tmp_ans = 0
    counts = [0] * len(rows)
    w = 0
    while w < W:
        for r in range(len(rows)):
            counts[r] += rows[r][w]
        if any([c > K for c in counts]):
            counts = [0] * len(rows)
            w -= 1
            tmp_ans += 1
        w += 1
 
    # 横に割った分を加算
    tmp_ans += len(div) - 2
    ans = min(ans, tmp_ans)
 
print(ans)
### BUGGY CODE ###

n,m,Q=map(int,input().split())

l=[]
r=[]
for i in range(m):
    a,b=map(int,input().split())
    l.append(a)
    r.append(b)

p=[]
q=[]    
for i in range(Q):
    c,d=map(int,input().split())
    p.append(c)
    q.append(d)

def ans(l,r,p,q):
    if p<=l and r<=q:
        return 1
    else:
        return 0


for i in range(Q):
    answer=0
    for j in range(m):
        answer+=int(ans(l[j],r[j],p[i],q[i])) 
    print(answer)

### FIXED CODE ###

n,m,Q=map(int,input().split())

l=[]
r=[]
for i in range(m):
    a,b=map(int,input().split())
    l.append(a)
    r.append(b)

p=[]
q=[]    
for i in range(Q):
    c,d=map(int,input().split())
    p.append(c)
    q.append(d)

grid=[[0]*(n+1) for i in range(n+1)]

for i in range(m):
    grid[l[i]][r[i]]+=1

for i in range(1,n+1):
    for j in range(1,n+1):
        grid[i][j]+=grid[i-1][j]
        grid[i][j]+=grid[i][j-1]
        grid[i][j]-=grid[i-1][j-1]
    
for i in range(Q):
    print(grid[q[i]][q[i]]-grid[q[i]][p[i]-1]-grid[p[i]-1][q[i]]+grid[p[i]-1][p[i]-1])
### BUGGY CODE ###

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

cnt = 0
L = []
R = []
# j - i = Ai + Aj --> i + Ai = j - Aj
for i in range(n):
    L.append(i + A[i])
    R.append(i - A[i])
    cnt += L.count(R[i])
#print(L, R)
print(cnt)


### FIXED CODE ###

from collections import defaultdict

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

cnt = 0
d = defaultdict(int)
# j - i = Ai + Aj --> i + Ai = j - Aj
for i in range(n):
    cnt += d[i - A[i]]
    d[i + A[i]] += 1

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

def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
#    L=[0]*(n1+1)
#    R=[0]*(n2+1)
    global L, R
    for i in range(n1):
        L[i]=A[left+i]
    for i in range(n2):
        R[i]=A[mid+i]
    L[n1]=float("inf")
    R[n2]=float("inf")
    i=0
    j=0
    global cnt
    for k in range(left,right):
        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

def mergeSort(A,left,right):
    if left+1<right:
        mid=(left+right)//2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
L=[0]*(n//2+2)
R=[0]*(n//2+2)
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)



### FIXED CODE ###

def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(float("inf"))
    R.append(float("inf"))
    """
    L=[0]*(n1+1)
    R=[0]*(n2+1)
    for i in range(n1):
        L[i]=A[left+i]
    for i in range(n2):
        R[i]=A[mid+i]
    L[n1]=float("inf")
    R[n2]=float("inf")
    """
    i=0
    j=0
    for k in range(left,right):
        global cnt
        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

def mergeSort(A,left,right):
    if left+1<right:
        mid=(left+right)//2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int, input().split()))
val = [[0 for i in range(n)] for j in range(k)]
v = [0 for _ in range(n)]

for i in range(n):
	for j in range(k):
		if i+j+1 <= n-1:
			val[j][i] = abs(h[i+j+1] - h[i])

for i in range(n):
	if i-1 >= 0:
		v[i] = min([v[i-j-1] + val[j][i-j-1] for j in range(min([k, i]))])
print(v[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int, input().split()))
v=[0]*n
for i in range(1,n):
	u = h[i]
	v[i] = min([v[j] + abs(h[j]-u) for j in range(max(0, i-k), i)])
print(v[n-1])
### BUGGY CODE ###

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

tmp = [0]*N
for i in range(N):
    tmp[i] = sum(A) - sum(A[:i+1])

ans = 0
mod = 10**9+7
for i in range(N):
    ans += (A[i]*tmp[i])%mod
    ans = ans%mod
    
print(ans)

### FIXED CODE ###

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

tmp = [0]*N
tmp2 = [0]*N
tmp2[0] = A[0]

for i in range(1,N):
    tmp2[i] = A[i] + tmp2[i-1]
sum_A = sum(A)

for i in range(N):
    tmp[i] = sum_A - tmp2[i]

ans = 0
mod = 10**9+7
for i in range(N):
    ans += (A[i]*tmp[i])%mod
    ans = ans%mod
    
print(ans)
### BUGGY CODE ###

def main():
	L = input()
	n = len(L)
	MOD = 10**9+7
	if L == "0":
		print(1)
		return

	num_1 = 0
	pos = []
	for i in range(n-1, -1, -1):
		if L[i] == "1":
			num_1 += 1
			pos.append(n-i-1)
	pos.reverse()
	ans = 2**(num_1)%MOD

	for i, p in enumerate(pos):
		cur = (1<<i)%MOD
		cur *= (3**p)%MOD
		cur %= MOD
		ans += cur
		ans %= MOD

	print(ans)


if __name__ == '__main__':
	main()

### FIXED CODE ###

MOD = 10**9+7

memo = dict()
memo[0] = 1
def pow3(n):
	if n in memo:
		return memo[n]
	if n%2 == 0:
		tmp = pow3(n//2)
		memo[n] = tmp*tmp%MOD
		return memo[n]
	memo[n] = 3 * pow3(n-1)%MOD
	return memo[n]

def cul(i, p):
	cur = (1<<i)%MOD
	cur *= pow3(p)
	return cur % MOD

def solve(L):
	n = len(L)
	if L == "0":
		return 1
	if not "0" in L:
		return pow3(n)

	num_1 = 0
	pos = []
	for i in range(n):
		if L[i] == "1":
			num_1 += 1
			pos.append(n-i-1)

	ans = (2**num_1)%MOD
	for i, p in enumerate(pos):
		ans += cul(i, p)
		ans %= MOD

	return ans

def main():
	L = input()
	print(solve(L))


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

import itertools

N = int(input())
balls = []

for i in range(N):
    x, y = map(int, input().split(' '))
    balls.append((x,y))

if N == 1:
    print("1")
    exit()

ans = 100
for l in list(itertools.permutations(balls)):
    dic = {}
    px = l[0][0]
    py = l[0][1]
    t_max = 1
    for i in range(1,len(l)):
        dx = l[i][0] - px
        px = l[i][0]
        dy = l[i][1] - py
        py = l[i][1]
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1
            if (t_max < dic[(dx,dy)]):
                t_max = dic[(dx,dy)]
        kitai = + N - i
        if ans < (N - kitai):
            break
    d_max = t_max
    cost = N - d_max
    if (cost < ans):
        ans = cost
        if (ans == 1):
            print(ans)
            exit()

print(ans)


### FIXED CODE ###

N = int(input())
balls = []
for i in range(N):
    x, y = map(int, input().split(' '))
    balls.append((x,y))

if N == 1:
    print("1")
    exit()

dic = {}
for i in range(N):
    for j in range(i+1,N):
        dx = balls[j][0] - balls[i][0]
        dy = balls[j][1] - balls[i][1]
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1
        dx *= -1
        dy *= -1
        if (dx,dy) not in dic.keys():
            dic[(dx,dy)] = 1
        else:
            dic[(dx,dy)] += 1

d_max = max(dic.values())
print(N - d_max)
### BUGGY CODE ###

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

a_set = sorted(set(a))
cnt_dict = {}


def f(n):
    return (n * (n - 1) // 2)


sum = 0
for i in a_set:
    cnt_dict[i] = a.count(i)
    sum += f(cnt_dict[i])


for i in a:
    print(sum - (cnt_dict[i] - 1))

### FIXED CODE ###

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

# a_set = sorted(set(a))

count = [0] * (n + 1)


def f(n):
    return (n * (n - 1) // 2)


sum = 0
for i in a:
    count[i] += 1
for i in count:
    sum += f(i)

for i in a:
    print(sum - (count[i] - 1))
### BUGGY CODE ###

h, w, m = map(int, input().split())
HW = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]

# print(h,w,m)
# HW.sort()
# print(*HW,sep='\n')
# print(HW)
# print('---')

# 個:h_ix
# 0: -
# 1: 2
# 2: 1
# 3: -    <- W
# 個:w_ix
# 0: -
# 1: 1,2,3
# 2: -    <- H

sum_h = [[0,0] for _ in range(h)] # [sum, index]
sum_w = [[0,0] for _ in range(w)]
for i in range(m):
    # print(h,w)
    h,w = HW[i]
    sum_h[h][0] += 1
    sum_w[w][0] += 1
    sum_h[h][1] = h
    sum_w[w][1] = w

# sum_h.sort(reverse=True)
# sum_w.sort(reverse=True)
# print(HW)
# print(sum_h)
# print(sum_w)
# print('---')

h_num_ix = {}
for num,ix in sum_h:
    if not num in h_num_ix:
        h_num_ix[num] = set()
    h_num_ix[num].add(ix)

w_num_ix = {}
for num,ix in sum_w:
    if not num in w_num_ix:
        w_num_ix[num] = set()
    w_num_ix[num].add(ix)

max_h_num = max(h_num_ix)
max_w_num = max(w_num_ix)

# print(h_num_ix)
# print(w_num_ix)
# print(max_h_num)
# print(max_w_num)

max_num = -1
for h_ix in h_num_ix[max_h_num]:
    for w_ix in w_num_ix[max_w_num]:
        num = max_h_num + max_w_num
        if [h_ix, w_ix] in HW:
            num -= 1
        max_num = max(max_num, num)
print(max_num)


### FIXED CODE ###

h, w, m = map(int, input().split())
HW = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]

sum_h = [[0,0] for _ in range(h)] # [sum, index]
sum_w = [[0,0] for _ in range(w)]
for i in range(m):
    h,w = HW[i]
    sum_h[h][0] += 1
    sum_w[w][0] += 1
    sum_h[h][1] = h
    sum_w[w][1] = w

h_num_ix = {}
for num,ix in sum_h:
    if not num in h_num_ix:
        h_num_ix[num] = set()
    h_num_ix[num].add(ix)

w_num_ix = {}
for num,ix in sum_w:
    if not num in w_num_ix:
        w_num_ix[num] = set()
    w_num_ix[num].add(ix)

max_h_num = max(h_num_ix)
max_w_num = max(w_num_ix)

# print(sorted(HW))
# print('---')
# print(h_num_ix)
# print(w_num_ix)
# print(max_h_num)
# print(max_w_num)
# print('====')

SHW = set()
for h,w in HW:
    SHW.add((h,w))
# print(SHW)

max_num = max_h_num + max_w_num - 1
for h_ix in h_num_ix[max_h_num]:
    for w_ix in w_num_ix[max_w_num]:
        num = max_h_num + max_w_num
        # if [h_ix, w_ix] in HW: continue
        if (h_ix, w_ix) in SHW: continue
        max_num += 1
        print(max_num)
        exit()
print(max_num)
### BUGGY CODE ###

n = int(input())

S = []
cnt = {}
for i in range(n):
    s = input()
    s = sorted(list(s))
    s = str(s)
    if s not in S:
        S.append(s)
        cnt[s] = 0
    else:
        cnt[s] += 1

ans = 0
for s in S:
    c = cnt[s]
    ans += c * (c+1) // 2

print(ans)

### FIXED CODE ###

n = int(input())

cnt = {}
for i in range(n):
    s = input()
    s = sorted(list(s))
    s = str(s)
    if s not in cnt:
        cnt[s] = 0
    else:
        cnt[s] += 1

ans = 0
for c in cnt.values():
    ans += c * (c+1) // 2

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

from collections import deque
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# check reachability B -> A ?
# 隣接和table
P = [B[(i-1)%N] + B[(i+1)%N] for i in range(N)]
D = deque(i for i in range(N) if B[i] - P[i] >= A[i])
ans = 0
nmatch = [B[i] == A[i] for i in range(N)].count(True)
while D:
    upd = False
    i = D.popleft()
    if B[i] == A[i]:
        nmatch += 1
        continue
    if B[i] <= P[i]:
        continue
    if B[i] - P[i] >= A[i]:
        P[(i-1)%N] -= P[i]
        P[(i+1)%N] -= P[i]
        B[i] -= P[i]
        upd = True
        ans += 1
        if B[i] == A[i]:
            nmatch += 1
        if B[(i-1)%N] - P[(i-1)%N] >= A[(i-1)%N]:
            D.append((i-1)%N)
        if B[(i+1)%N] - P[(i+1)%N] >= A[(i+1)%N]:
            D.append((i+1)%N)
        if B[i] - P[i] >= A[i]:
            D.append(i)
    if not upd:
        break

print(ans if nmatch == N else -1)


### FIXED CODE ###

from collections import deque
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# check reachability B -> A ?
# 隣接和table
P = [B[(i-1)%N] + B[(i+1)%N] for i in range(N)]
D = deque(i for i in range(N) if B[i] - P[i] >= A[i])
ans = 0
nmatch = [B[i] == A[i] for i in range(N)].count(True)
while D:
    upd = False
    i = D.popleft()
    if B[i] == A[i]:
        nmatch += 1
        continue
    if B[i] <= P[i]:
        continue
    if B[i] - P[i] >= A[i]:
        n = (B[i] - A[i]) // P[i]
        P[(i-1)%N] -= P[i] * n
        P[(i+1)%N] -= P[i] * n
        B[i] -= P[i] * n
        upd = True
        ans += n
        if B[i] == A[i]:
            nmatch += 1
        if B[(i-1)%N] - P[(i-1)%N] >= A[(i-1)%N]:
            D.append((i-1)%N)
        if B[(i+1)%N] - P[(i+1)%N] >= A[(i+1)%N]:
            D.append((i+1)%N)
    if not upd:
        break

print(ans if nmatch == N else -1)
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split()]
def Check(K):
  stack=[]
  n=A[0]
  for i in range(1,N):
    if A[i-1]<A[i]:
      n=A[i]
    else:
      if K==1:
        return False
      while n>A[i]:
        if stack:
          if stack[-1][0]==n:
            stack.pop()
        n-=1
      k=n
      while k>=1:
        if not stack:
          stack.append([k,1])
          break
        if stack[-1][0]==k:
          if stack[-1][1]==K-1:
            if k!=1:
              stack.pop()
              k-=1
            else:
              return False
          else:
            stack[-1][1]+=1
            break
        else:
          stack.append([k,1])
          break
  return True
l,r=1,N
while l<r:
  m=(l+r)//2
  if Check(m):
    r=m
  else:
    l=m+1
print(l)
          
          
          
      

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
def Check(K):
  stack=[]
  n=A[0]
  for i in range(1,N):
    if A[i-1]<A[i]:
      n=A[i]
    else:
      if K==1:
        return False
      n=A[i]
      while True:
        l=0
        if stack:
          l=stack[-1][0]
        if l>n:
          stack.pop()
        else:
          break       
      k=n
      while k>=1:
        if not stack:
          stack.append([k,1])
          break
        if stack[-1][0]==k:
          if stack[-1][1]==K-1:
            if k!=1:
              stack.pop()
              k-=1
            else:
              return False
          else:
            stack[-1][1]+=1
            break
        else:
          stack.append([k,1])
          break
  return True
l,r=1,N
while l<r:
  m=(l+r)//2
  if Check(m):
    r=m
  else:
    l=m+1
print(l)
### BUGGY CODE ###

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

num_count = [0]*(10**5+1)
for i in A:
    num_count[i] += 1

for q in range(Q):
    B,C = map(int,input().split())
    num_count[C] += num_count[B]
    num_count[B] = 0
    ans = 0
    for i in range(10**5+1):
        ans += i*num_count[i]
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
import numpy as np

num_count = [0]*(10**5+1)
num_count = np.array(num_count)
tmp = np.arange(10**5+1)
tmp_sum = sum(A)
for i in A:
    num_count[i] += 1

for q in range(Q):
    B,C = map(int,input().split())
    tmp_C = C*(num_count[B])
    tmp_B = B*(num_count[B])
    num_count[C] += num_count[B]
    num_count[B] = 0
    tmp_sum = tmp_sum + tmp_C - tmp_B
    print(tmp_sum)
### BUGGY CODE ###

N=int(input())
P=list(map(float,input().split()))
dp=[[0]*(N+1) for i in range(N+1)]
dp[0][0]=1
for i in range(1,N+1):
  for j in range(N+1):
    dp[i][j]=dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
ans=0

for i in range(N//2+1,N+1):
  ans+=dp[-1][i]
print(ans)

### FIXED CODE ###

N=int(input())
P=list(map(float,input().split()))
dp=[[0]*(N+1) for i in range(N+1)]
dp[0][0]=1
for i in range(1,N+1):
  for j in range(N+1):
    dp[i][j]=dp[i-1][j-1]*P[i-1]+dp[i-1][j]*(1-P[i-1])
ans=0

for i in range(N//2+1,N+1):
  ans+=dp[-1][i]
print(ans)
### BUGGY CODE ###

import numpy as np
from sys import stdin

N, Q = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()

def func(Str):
  idx = Str.find("AC")
  return idx

i = 0
ac_idx = []
while i<N:
  a = func(S[i:])
  if a != -1:
    ac_idx.append(a+i)
    i = a+i+2
  else:
    break

ac_idx = np.array(ac_idx)
for j in range(Q):
  l,r = [int(x) for x in stdin.readline().rstrip().split()]
  print(np.sum((ac_idx>=l-1)&(ac_idx<r-1)))
  

### FIXED CODE ###

from sys import stdin

N, Q = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()

ac_idx = [0]
count = 0

for i in range(N-1):
  if S[i]=="A" and S[i+1]=="C":
    count+=1
  ac_idx.append(count)

for j in range(Q):
  l,r = [int(x) for x in stdin.readline().rstrip().split()]
  print(ac_idx[r-1]-ac_idx[l-1])
### BUGGY CODE ###

x = int(input())


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort()
    return array


divs = divisors(x)

for div in divs:
    for a in range(div+1):
        b = a - div
        if a ** 5 - b ** 5 == x:
            print(a, b)
            exit()


### FIXED CODE ###

x = int(input())

for a in range(-200, 200):
    for b in range(-200, 200):
        if a**5 - b**5 == x:
            print(a, b)
            exit()
### BUGGY CODE ###

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

dp = [float("inf")] * ((1<<n) + 1)
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c_list = list(map(int, input().split()))
    c = 0
    for j in range(b):
        c += 1 << (c_list[j]-1)

    for j in range(1<<n):
        dp[j | c] = min(dp[j] + a, dp[j | c])

if dp[(1<<n) - 1] == float("inf"):
    ans = -1
else:
    ans = dp[(1<<n) - 1]

print(ans)


### FIXED CODE ###

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

dp = [float("inf")] * ((1<<n) + 1)
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c_list = list(map(int, input().split()))
    c = 0
    for j in range(b):
        c += 1 << (c_list[j]-1)

    for j in range(1<<n):
        dp[j | c] = min(dp[j] + a, dp[j | c])

if dp[(1<<n) - 1] == float("inf"):
    ans = -1
else:
    ans = dp[(1<<n) - 1]

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

N = input()

data = map(int,raw_input().split())
data.sort()

ans = 0
pnum = -1
for i in data:
    if pnum != i:
        count = data.count(i)
        if count < i:
            ans += count
        else:
            ans += count-i
        pnum = i

print ans

### FIXED CODE ###

N = input()

data = map(int,raw_input().split())
data.sort()

count = []
num = []
pnum = -1
counter = -1

for i in data:
    if pnum != i:
        pnum = i
        num.append(i)
        count.append(1)
        counter += 1
    else:
        count[counter] += 1

ans = 0

for i in range(len(num)):
    if count[i] < num[i]:
        ans += count[i]
    else:
        ans += count[i]-num[i]

print ans
### BUGGY CODE ###

n = int(input())
A = []
cnt = 0
for i in range(n):
    m = input()
    if m not in A:
        A.append(m)
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
A = [input() for i in range(n)]
print(-len(A) + len(set(A)) + n)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
r=2*10**14
if n==2:
    print(abs(A[0]-A[1]))
else:
    for i in range(1,n-1):
        s=abs(sum(A[:i])-sum(A[i:]))
        r=min(r,s)
    print(r)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
L=[A[0]]
R=[A[-1]]
for i in range(1,n-1):
    l=L[i-1]+A[i]
    L.append(l)
    r=R[i-1]+A[-(i+1)]
    R.append(r)
c=2*10**14
for i in range(n-1):
    s=abs(L[i]-R[-(i+1)])
    c=min(c,s)
print(c)
### BUGGY CODE ###

N,K = map(int, input().split())
l = list(map(int,input().split()))
 
def E(n):
  return sum(range(1,n+1)) / n
 
j = sum(l[0:0+K])
m = 0
if N == 1:
  l2 = list(map(E, l))
  print(sum(l2))
elif N == K:
  l2 = list(map(E, l))  
  print(sum(l2))
else:
  for i in range(1,len(l)-(K-1)):
      j = j - l[i-1] + l[i+K-1]
      if l[i] < l[i-1]:
          continue
      elif m < j:
          m = j
          t = l[i:i+K]

  l2 = list(map(E, t))
 
  print(sum(l2))

### FIXED CODE ###

N,K = map(int, input().split())
l = list(map(int,input().split()))
 
def E(n):
  return (1 + n) / 2
 
j = sum(l[0:0+K])
m = 0
if N == 1:
  l2 = list(map(E, l))
  print(sum(l2))
elif N == K:
  l2 = list(map(E, l))  
  print(sum(l2))
else:
  for i in range(1,len(l)-(K-1)):
      j = j - l[i-1] + l[i+K-1]
      if l[i] < l[i-1]:
          continue
      elif m < j:
          m = j
          t = l[i:i+K]

  l2 = list(map(E, t))
 
  print(sum(l2))