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

N = int(input())
A = [int(a) for a in input().split()]
mod = 10**9+7
SUM = 0

maxA = max(A)
d = 0
while 1:
    if maxA < 2**d:
        break
    d += 1

BitA = [[0]*d for _ in range(N)]
for i in range(N):
    for j in range(d):
        BitA[i][j] = int(bin(A[i]|2**d)[3+j])

BitSumB = 0
for i in range(d):
    tmp = sum([BitA[j][i] for j in range(N)])
    BitSumB += 2 ** (d-i-1) * (tmp * (N - tmp))

print(BitSumB % mod)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
mod = 10**9+7
SUM = 0

maxA = max(A)
d = 0
while 1:
    if maxA < 2**d:
        break
    d += 1

BitSumB = 0
for i in range(d):
    tmp = 0
    for n in range(N):
        tmp += (A[n] >> i) & 1
    BitSumB += (2**i) * tmp * (N - tmp)



"""
BitA = [[0]*d for _ in range(N)]
for i in range(N):
    BitA[i] = list(map(int, format(bin(A[i])[2:], '0>{}'.format(d))))

BitSumB = 0
for i in range(d):
    tmp = sum([BitA[j][i] for j in range(N)])
    BitSumB += 2 ** (d-i-1) * (tmp * (N - tmp))
    #BitSumB = BitSumB % mod
"""

print(BitSumB % mod)
### BUGGY CODE ###

def main():
    N = int(input())
    S = input()

    c = 0

    for i in range(N):
        for j in range(i, N):
            for k in range(j, N):
                if j - i != k - j and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                    c += 1

    print(c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()

    c = 0

    r_indices = tuple([i for i in range(N) if S[i] == 'R'])
    g_indices = tuple([i for i in range(N) if S[i] == 'G'])
    b_indices = tuple([i for i in range(N) if S[i] == 'B'])

    # print(r_indices)
    # print(g_indices)
    # print(b_indices)

    avoid = 0

    for center in range(1, N - 1):
        # print('###')
        # print('center = ', center)
        # print(min(center, N - center - 1))

        for width in range(1, min(center + 1, N - center)):
            # print('c, w = ', center, width)
            little = center - width
            great = center + width
            # print('little=', little)
            # print('center=', center)
            # print('great=', great)

            if S[little] != S[great] and S[center] != S[great] and S[little] != S[center]:
                avoid += 1

    total = len(r_indices) * len(g_indices) * len(b_indices)

    print(total - avoid)


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

import numpy as np

N, W = map(int, input().split())
dp = np.zeros((N,W+1))
for i in range(N):
  w, v = map(int, input().split())
  for j in range(1,W+1):
    if j-w >= 0:
      dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
    else:
      dp[i][j] = dp[i-1][j]
print(int(dp[-1][-1]))

### FIXED CODE ###

import numpy as np
n, w = map(int, input().split())
dp = np.zeros(w+1)

for i in range(1,n+1): #n個の荷物をそれぞれ持つか否か
  wn, vn = map(int, input().split())
  dp[wn:] = np.maximum(dp[wn:], dp[:-wn]+vn)#wnより小さい=>持てない=>価値変わらない
print(int(dp[-1]))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
bc=[]

for i in range(m):
    b,c=map(int,input().split())
    bc+=[c]*b
num=min(len(bc),n)
bc=sorted(bc,reverse=True)[:num]

ans=sum(a)
temp=sum(a)
for i in range(n):
    if num<=i:continue
    temp+=-a[i]+bc[i]
    if temp>ans:ans=temp
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
bc=[list(map(int,input().split())) for i in range(m)]
bc=sorted(bc,reverse=True,key=lambda x:x[1])
c=[]

cnt=0
for B,C in bc:
    for i in range(B):
        if cnt==n:break
        cnt+=1
        c.append(C)
c=sorted(c,reverse=True)

ans=sum(a)
temp=ans
for i in range(n):
    if cnt<=i:continue
    temp+=-a[i]+c[i]
    if temp>ans:ans=temp
print(ans)
### BUGGY CODE ###

s = list(input().strip())
q = int(input().strip())
queries = []
one_count = 0
one_counts = []
for i in range(q):
    inp = input().split()
    queries.append(inp)
    if inp[0] == "1":
        one_count += 1
    one_counts.append(one_count)
one_counts = list(map(lambda x: (one_count - x), one_counts))
if one_count % 2 == 1:
    s = s[::-1]
pre = []
suf = []
for i in range(q):
    if queries[i][0] == "1":
        continue
    elif queries[i][0] == "2":
        if queries[i][1] == "1":
            if one_counts[i] % 2 == 0:
                pre.insert(0, queries[i][2])
            else:
                suf.append(queries[i][2])
        elif queries[i][1] == "2":
            if one_counts[i] % 2 == 0:
                suf.append(queries[i][2])
            else:
                pre.insert(0, queries[i][2])
print("".join(pre + s + suf))


### FIXED CODE ###

s = list(input().strip())
q = int(input().strip())
queries = []
one_count = 0
one_counts = []
for i in range(q):
    inp = input().split()
    queries.append(inp)
    if inp[0] == "1":
        one_count += 1
    one_counts.append(one_count)
one_counts = list(map(lambda x: (one_count - x), one_counts))
if one_count % 2 == 1:
    s = s[::-1]
pre = []
suf = []
for i in range(q):
    if queries[i][0] == "1":
        continue
    elif queries[i][0] == "2":
        if queries[i][1] == "1":
            if one_counts[i] % 2 == 0:
                pre.append(queries[i][2])
            else:
                suf.append(queries[i][2])
        elif queries[i][1] == "2":
            if one_counts[i] % 2 == 0:
                suf.append(queries[i][2])
            else:
                pre.append(queries[i][2])
print("".join(pre[::-1] + s + suf))
### BUGGY CODE ###

s=input()
ret=0
while "BW" in s:
    ret+=s.count("BW")
    s=s.replace("BW","WB")
print(ret)

### FIXED CODE ###

s=input()
n=len(s)
ret=0
pos=0
for i in range(n):
    if s[i]=="W":
        ret+=i-pos
        pos+=1
print(ret)
### BUGGY CODE ###

def func():
    return

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

'''
for i in range(n-1):
    for j in range(i+1, n):
        if a[i] == a[j]:
            print("NO")
            exit()
'''
for i in range(n-1):
    if a[i] in a[i+1:]:
        print("NO")
        exit()

print("YES")

### FIXED CODE ###

def func():
    return

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

ascA = sorted(a)
for i in range(n-1):
    if ascA[i] == ascA[i+1]:
        print("NO")
        exit()

'''
for i in range(n-1):
    for j in range(i+1, n):
        if a[i] == a[j]:
            print("NO")
            exit()
'''
'''
ans = [0]*(max(a)+1)
for ida in a:
    if ans[ida] > 0:
        print("NO")
        exit()
    ans[ida] += 1
'''

print("YES")
### BUGGY CODE ###

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

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


h, w = MI()
Ch, Cw = MI()
Dh, Dw = MI()

S = [["#"] * (w + 4), ["#"] * (w + 4)]
for _ in range(h):
    S.append(["#", "#"] + list(ST()) + ["#", "#"])
S.append(["#"] * (w + 4))
S.append(["#"] * (w + 4))

dxy = ((0, 1), (0, -1), (1, 0), (-1, 0), (0, 0))
wxy = tuple(
    (x, y)
    for x, y in itertools.product([-2, -1, 0, 1, 2], repeat=2)
    if (x, y) not in dxy
)
dxy = ((0, 1), (0, -1), (1, 0), (-1, 0))

wq = {(Ch + 1, Cw + 1)}
cost = 0
while wq:
    q = list(wq)
    passed = []
    while q:
        qq = []
        for y, x in q:
            if y == Dh + 1 and x == Dw + 1:
                print(cost)
                exit()
            passed.append((y, x))
            S[y][x] = "#"
            for dy, dx in dxy:
                ny, nx = y + dy, x + dx
                if S[ny][nx] == "#":
                    continue
                # if ny == Dh + 1 and nx == Dw + 1:
                #     print(cost)
                #     exit()
                qq.append((ny, nx))
                # S[ny][nx] = "#"
        q = qq

    # print(cost, set(passed))
    wq = set()
    for y, x in passed:
        for dy, dx in wxy:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == "#":
                continue
            wq.add((ny, nx))

    cost += 1

print(-1)


### FIXED CODE ###

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

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


h, w = MI()
Ch, Cw = MI()
Dh, Dw = MI()

S = [["#"] * (w + 4), ["#"] * (w + 4)]
for _ in range(h):
    S.append(["#", "#"] + list(ST()) + ["#", "#"])
S.append(["#"] * (w + 4))
S.append(["#"] * (w + 4))

dxy = ((0, 1), (0, -1), (1, 0), (-1, 0), (0, 0))
wxy = tuple(
    (x, y)
    for x, y in itertools.product([-2, -1, 0, 1, 2], repeat=2)
    if (x, y) not in dxy
)
dxy = ((0, 1), (0, -1), (1, 0), (-1, 0))

wq = {(Ch + 1, Cw + 1)}
cost = 0
while wq:
    q = wq
    passed = set()
    while q:
        qq = set()
        for y, x in q:
            if y == Dh + 1 and x == Dw + 1:
                print(cost)
                exit()
            passed.add((y, x))
            S[y][x] = "#"
            for dy, dx in dxy:
                ny, nx = y + dy, x + dx
                if S[ny][nx] == "#":
                    continue
                # if ny == Dh + 1 and nx == Dw + 1:
                #     print(cost)
                #     exit()
                qq.add((ny, nx))
                # S[ny][nx] = "#"
        q = qq

    # print(cost, set(passed))
    wq = set()
    for y, x in passed:
        for dy, dx in wxy:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == "#":
                continue
            wq.add((ny, nx))

    cost += 1

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

import math
n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
pgcd = True
sgcd = a[n-1]

for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    for j in range(i+1,n):
        if math.gcd(a[i], a[j]) != 1:
            pgcd = False

if pgcd:
    print('pairwise coprime')
elif sgcd==1:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

import math

n = int(input().rstrip())
a = list(map(int,input().rstrip().split()))
NUM = 1_000_005
aa = [0]*NUM
pgcd = True
sgcd = a[n-1]
aa[a[n-1]]+=1
for i in range(0,n-1):
    sgcd = math.gcd(sgcd, a[i])
    aa[a[i]]+=1

for i in range(2,NUM):
    tmp = sum(aa[i::i])
    if tmp >= 2:
        pgcd = False
        break
        
if sgcd!=1:
    print('not coprime')
elif pgcd:
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))
B = len(A)
ans = 1
a = 0
for a in range(B) :
    ans = ans*A[a]
    a += 1
if ans > 10**18 :
    ans = -1
print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))
B = len(A)
ans = 1
a = 0
for a in range(B) :
    ans = ans*A[a] 
    if ans > 10**18 :
        if 0 in A :
            ans = 0
        else :
            ans = -1 
        break
    else :
        a += 1
print(ans)
### BUGGY CODE ###

import bisect

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

for i in range(m):
    x=a[-(i+1)]//2
    bisect.insort(a,x)
print(sum(a[:n]))

### FIXED CODE ###

import heapq

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

import bisect

n, m = map(int, input().split())
a_array = sorted([int(x) for x in input().split()])
bc_array = sorted([[int(x) for x in input().split()] for x in range(m)], key=lambda x: x[1], reverse=True)

candidate_replace_cnt = n
replace_sum = 0
replace_cnt = 0
for b, c in bc_array:
    if a_array[0] > c and candidate_replace_cnt <= 0:
        break
    # 何枚入れられそうか
    num = bisect.bisect_left(a_array, c)
    # 入れ替えられる最大枚数が決まる
    candidate_replace_cnt = min(candidate_replace_cnt, num)
    # 全部入れ替えられる
    if candidate_replace_cnt <= b:
        replace_sum += c*candidate_replace_cnt
        a_array = a_array[candidate_replace_cnt:]
        break
    candidate_replace_cnt -= b
    replace_sum += c*b
    a_array = a_array[b:]
print(replace_sum + sum(a_array))


### FIXED CODE ###

import bisect

n, m = map(int, input().split())
a_array = sorted([int(x) for x in input().split()])
bc_array = sorted([[int(x) for x in input().split()] for x in range(m)], key=lambda x: x[1], reverse=True)

# 何枚入れ替えられるか
candidate_replace_cnt = n
for b, c in bc_array:
    if a_array[0] >= c or candidate_replace_cnt < 0:
        break
    for i in range(b):
        a_array.append(c)
    candidate_replace_cnt -= b
a_array.sort(reverse=True)
print(sum(a_array[:n]))
### BUGGY CODE ###

#!/usr/bin/env python3
s = input()
n = len(s)
cs = [0] * (n + 1)
for i, x in enumerate(map(int, list(s))):
    cs[i + 1] = cs[i] + x
ans = 0
for i in range(n):
    for j in range(i + 3, n + 1):
        if (cs[j] - cs[i]) % 3 != 0:
            continue
        k = int(s[i:j])
        if k % 2019 == 0:
            ans += 1
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
s = input()[::-1]
n = len(s)
cs = [0] * (n + 1)
ten = 1
for i in range(n):
    cs[i + 1] = int(s[i]) * ten % 2019
    ten = ten * 10 % 2019
for i in range(n):
    cs[i + 1] = (cs[i + 1] + cs[i]) % 2019
cnt = [0] * 2019
for i, x in enumerate(cs):
    cnt[x] += 1
ans = sum(x * (x - 1) // 2 for x in cnt)
print(ans)
### BUGGY CODE ###

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

a.sort()
b.sort()
c.sort()
from bisect import bisect_left
count = 0
for ci in range(n):
  b_right = bisect_left(b, c[ci]) - 1
  if b_right < 0:
    continue
  for bi in range(b_right+1):
    a_right = bisect_left(a, b[bi]) - 1
    an = a_right + 1
    if a_right < 0:
      continue
    count += an
print(count)

### FIXED CODE ###

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

a.sort()
b.sort()
c.sort()
from bisect import bisect_left
from bisect import bisect_right
count = 0
for bi in range(n):
  c_right = bisect_right(c, b[bi])
  a_left = bisect_left(a, b[bi])
  count += (n-c_right) * a_left
print(count)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
cs = list(map(int, input().split()))
bs = list(map(int, input().split()))
a_s = list(map(int, input().split()))
a_s.sort(reverse=True)
bs.sort(reverse=True)
cs.sort(reverse=True)

list = []
i = -1
# flag = True
minlist = 0
for a in a_s:
    if minlist >= (a + bs[0] + cs[0]):
        break
    for b in bs:
        if minlist >= (a + b + cs[0]):
            break
        for c in cs:
            abc = a + b +c
            if i >= k:
            # if flag and i >= k:
                list.sort(reverse=True)
                minlist = list[k]
                # flag = False
            if minlist >= abc:
                break
            list.append(abc)
            i += 1
list.sort(reverse=True)
for i in range(k):
    print(list[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = []
for ai in a:
  for bi in b:
    ab.append(ai + bi)
ab.sort(reverse = True)

abc = []

for abi in ab[:k]:
  for ci in c:
    abc.append(abi + ci)
abc.sort(reverse = True)

for abci in abc[:k]:
  print(abci)
### BUGGY CODE ###

s = input()

slength = len(s)
for _ in range(5000):
    s = s.replace("01", "").replace("10", "")
print(slength-len(s))

### FIXED CODE ###

s = input()
n0 = s.count("0")
print(2*min(n0, len(s)-n0))
### BUGGY CODE ###

# ABC 051: B – Sum of Three Integers
k, s = [int(s) for s in input().split()]
number = 0

for a in range(k + 1):
    for b in range(k + 1):
        for c in range(k + 1):
            if a + b + c == s:
                number += 1

print(number)

### FIXED CODE ###

# ABC 051: B – Sum of Three Integers
k, s = [int(s) for s in input().split()]
number = 0

for a in range(k + 1):
    for b in range(k + 1):
            if 0 <= (s - a - b) <= k:
                number += 1

print(number)
### BUGGY CODE ###

MOD = 10**9 + 7
n, oddness = [int(item) for item in input().split()]
# Oddness must be even
if oddness % 2 ==  1:
    print(0)
    exit()
oddness //= 2
max_oddness = 1250 + n
max_pending = n//2 + 2

dp = [[[0] * (max_oddness) for _ in range(max_pending)] for _ in range(n)]
dp[0][0][0] = 1
dp[0][1][1] = 1
for i in range(1, n):
    for j in range(min(i+1, n//2+1)):
        for k in range(oddness+1):
            # Oddness increase by num of pending item
            # Connect in line 
            dp[i][j][k+j] += dp[i-1][j][k]
            # Choose 1 from pending items
            dp[i][j][k+j] += dp[i-1][j][k] * j * 2
            dp[i][j][k+j] %= MOD
            # Choose 2 from pending items
            if j > 0:
                dp[i][j-1][k+j-1] += dp[i-1][j][k] * j*j
            # Do nothing 
            dp[i][j+1][k+j+1] += dp[i-1][j][k] 

print(dp[n-1][0][oddness] % MOD)

### FIXED CODE ###

MOD = 10**9 + 7
n, oddness = [int(item) for item in input().split()]
# Oddness must be even
if oddness % 2 ==  1:
    print(0)
    exit()
oddness //= 2
max_oddness = n*n + n
max_pending = n + 1

dp = [[[0] * (max_oddness) for _ in range(max_pending)] for _ in range(n)]
oddness_itr = [item for item in range(n*n)]
for i in range(n):
    if i == 0:
        dp[0][0][0] = 1
        dp[0][1][1] = 1
        continue
    for j in range(i+1):
        for k in oddness_itr:
            # Connect in line
            # Oddness increase by num of pending item
            dp[i][j][k+j] += dp[i-1][j][k]
            # Choose 1 from pending
            dp[i][j][k+j] += dp[i-1][j][k] * j*2 
            dp[i][j][k+j] %= MOD
            # Choose 2 from pending
            if j > 0:
                dp[i][j-1][k+j-1] += dp[i-1][j][k] * j*j
                dp[i][j-1][k+j-1] %= MOD 
            # Do nothing 
            dp[i][j+1][k+j+1] += dp[i-1][j][k] 
            dp[i][j+1][k+j+1] %= MOD 

print(dp[n-1][0][oddness])
### BUGGY CODE ###

def binarySearch(key, lst):
    start = 0
    end = len(lst) - 1
    while end - start >= 0:
        i = (end - start) / 2 + start
        if lst[i] > key:
            end = i - 1
        elif lst[i] < key:
            start = i + 1
        else:
            return True
    return False

if __name__ == "__main__":
    input()
    S = map(int, raw_input().split())
    input()
    T = map(int, raw_input().split())

    n = 0
    for t in T:
        if binarySearch(t, S[:]):
            n += 1
    print n

### FIXED CODE ###

def binarySearch(key, lst):
    start = 0
    end = len(lst) - 1
    while end - start >= 0:
        i = (end - start) / 2 + start
        if lst[i] > key:
            end = i - 1
        elif lst[i] < key:
            start = i + 1
        else:
            del lst[i]
            return True
    return False

if __name__ == "__main__":
    input()
    S = map(int, raw_input().split())
    input()
    T = map(int, raw_input().split())

    n = 0
    for t in T:
        if binarySearch(t, S):
            n += 1
    print n
### BUGGY CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
C = Counter(A)

ind = 0
for i, x in enumerate(A):
    if C[x] > 1:
        ind = i - ind

mod = 10 ** 9 + 7


def nCr(a, b):
    p = q = 1
    for i in range(a - b + 1, a + 1):
        p *= i
        p %= mod
    for i in range(2, b + 1):
        q *= i
        q %= mod
    return p * pow(q, mod - 2, mod) % mod


for i in range(1, n + 2):
    res = nCr(n + 1, i) - nCr(n - ind, i - 1)
    res %= mod
    print(res)


### FIXED CODE ###

from collections import Counter
import numpy as np

N = 10 ** 6
Nsq = 10 ** 3
mod = 10 ** 9 + 7

fac = np.arange(N, dtype=np.int64).reshape(Nsq, Nsq)
fac[0, 0] = 1
for i in range(1, Nsq):
    fac[:, i] *= fac[:, i - 1]
    fac[:, i] %= mod
for i in range(1, Nsq):
    fac[i] *= fac[i - 1, -1]
    fac[i] %= mod
fac = fac.ravel()

finv = np.arange(1, N + 1, dtype=np.int64)[::-1].reshape(Nsq, Nsq)
finv[0, 0] = pow(int(fac[N - 1]), mod - 2, mod)
for i in range(1, Nsq):
    finv[:, i] *= finv[:, i - 1]
    finv[:, i] %= mod
for i in range(1, Nsq):
    finv[i] *= finv[i - 1, -1]
    finv[i] %= mod
finv = finv.ravel()[::-1]


def nCr(a, b):
    if b > a:
        return 0
    else:
        comb = fac[a] * finv[b] % mod * finv[a - b] % mod
        return comb


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

ind = 0
for i, x in enumerate(A):
    if C[x] > 1:
        ind = i - ind

for i in range(1, n + 2):
    res = nCr(n + 1, i) - nCr(n - ind, i - 1)
    res %= mod
    print(res)
### BUGGY CODE ###

import bisect

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

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

nums.sort()
for i in range(m):
    b, c = map(int, input().split())
    
    index = bisect.bisect_left(nums, c)
    if index > 0:
        temp = nums[0:index]
        temp.extend([c]*b)
        temp.extend(nums[index:])
        nums = temp[-n:]
        
result = 0
for i in nums:
    result = result + i

print(result)

### FIXED CODE ###

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

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

ops = []
for i in nums:
    ops.append([1, i])
    
for i in range(m):
    b, c = map(int, input().split())
    ops.append([b, c])

total = 0
sums = []
for b, c in sorted(ops, key=lambda x:x[1], reverse=True):
    if total > n:
        break
    sums.extend([c]*b)
    total = total + b
print(sum(sums[:n]))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
A_num = list(set(A.copy()))
A_num_size = len(A_num)
for i in range(N):
    out = 0
    j = 0
    while j < A_num_size:
        if A.count(A_num[j]) == 1:
            A_num.remove(A_num[j])
            A_num_size -= 1
            if A_num_size == 0:
                break
            else:
                continue
        if A_num[j] == A[i]:
            out += int((A.count(A_num[j]) * (A.count(A_num[j]) - 1) / 2 - (A.count(A_num[j]) - 1)))
        else:
            out += int((A.count(A_num[j]) * (A.count(A_num[j]) - 1) / 2))
        j += 1
    print(out)

### FIXED CODE ###

'''
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split(' '))))
num_sum = 0
remove_array = np.array([], int)
for i in range(N):
    c1 = np.count_nonzero(A == i + 1)
    c2 = np.count_nonzero(A == A[i])
    if c2 <= 1:
        remove_array = np.append(remove_array, 0)
    else:
        remove_array = np.append(remove_array, c2 - 1)
    num_sum += int(c1 * (c1 - 1) / 2)
print(*(num_sum - remove_array), sep='\n')
'''
import collections
N = int(input())
A = list(map(int, input().split()))
cnt = collections.Counter(A)
total = 0
for key in cnt.keys():
    total += cnt[key] * (cnt[key] - 1) // 2
for i in range(N):
    tmp = total
    tmp -= cnt[A[i]] * (cnt[A[i]] - 1) // 2
    tmp += (cnt[A[i]] - 1) * (cnt[A[i]] - 2) // 2
    print(tmp)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

for i in range(Q):
	count = 0
	l, r = map(int, input().split())
	Sr = S[l-1:r]
	for j in range(len(Sr)-1):
		if(Sr[j] == 'A' and Sr[j+1] == 'C'):
			count += 1
	print(count)
	

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0]*(N+1)
for i in range(N):
	t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])