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

#!/usr/bin/env python3
import math

def main():
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        sa = input().split(' ')
        l.append(int(sa[0]))
        r.append(int(sa[1]))

    r_max = 100000
    primes = [True for i in range(r_max)]
    primes[0] = False
    primes[1] = False
    i = 2
    max_i = int(math.sqrt(r_max))
    while i <= max_i:
        for j in range(i * i, r_max, i):
            primes[j] = False
        while i <= max_i:
            i += 1
            if primes[i]:
                break

    for i in range(Q):
        c = 0
        for j in range(l[i], r[i] + 1, 2):
            if primes[j] and primes[int((j + 1) / 2)]:
                c += 1
        print(c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import math

def main():
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        na = list(map(int, input().split()))
        l.append(na[0])
        r.append(na[1])

    r_max = 100000
    primes = [True for i in range(r_max)]
    like_numbers = [0 for i in range(r_max)]

    primes[0] = primes[1] = False
    max_i = int(math.sqrt(r_max))
    i = 2
    while i <= max_i:
        primes[i] = True
        for j in range(i * i, r_max, i):
            primes[j] = False
        while i <= max_i:
            i += 1
            if primes[i]:
                break

    for i in range(3, r_max, 2):
        if primes[i] and primes[int((i + 1) / 2)]:
            like_numbers[i] = 1

    c = 0
    for i in range(3, r_max, 2):
        if like_numbers[i]:
            c += 1
        like_numbers[i] = c


    for i in range(Q):
        if l[i] == 1:
            print(like_numbers[r[i]])
        else:
            print(like_numbers[r[i]] - like_numbers[l[i] - 2])

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

n, a, b = map(int, input().split())
ans = []

def add_ball(a, b):
    ball_list = []
    for i in range(a):
        ball_list.append('b')
        if len(ball_list) == n:
            return ball_list
    for j in range(b):
        ball_list.append('r')
        if len(ball_list) == n:
            return ball_list
    return ball_list


for i in range((n // (a + b)) + 1):
    ball_list = add_ball(a, b)
    ans += ball_list

print(ans[:n].count('b'))

### FIXED CODE ###

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

ans = n // (a + b) * a
rem = n % (a + b)
ans += min(a, rem)  # ansとremを比較することでnの位置よって処理を変えられる

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

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = float("inf")

dp = [INF] * N
dp[0] = 0
for i in range(1, N):
    for j in range(K):
        if i - j-1 < 0:
            break # スタート地点より手前になる場合は飛ばす
        dp[i] = min(dp[i], dp[i-j-1] + abs(h[i] - h[i-j-1]))

print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = float("inf")

dp = [INF] * N
dp[0] = 0
for i in range(1, N):
    for j in range(K):
        if i - j-1 < 0:
            break # スタート地点より手前になる場合は飛ばす
        dp[i] = min(dp[i], dp[i-j-1] + abs(h[i] - h[i-j-1]))

print(dp[-1])
### BUGGY CODE ###

n, m = map(int, input().split())
l1, r1 = map(int, input().split())
ans = set(range(l1, r1+1))
for  i in range(2, m+1):
    l, r = map(int, input().split())
    can_pass = set(range(l, r+1))
    ans = ans.intersection(can_pass)

print(len(ans))

### FIXED CODE ###

n, m = map(int, input().split())
l, r = map(int, input().split())
for i in range(m-1):
    l_c, r_c = map(int, input().split()) 
    l = max(l, l_c)
    r = min(r, r_c)
print(max(r-l+1, 0))
### BUGGY CODE ###

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

A=[list(map(int,input().split())) for _ in range(H)]
B=[list(map(int,input().split())) for _ in range(H)]

#dp[i][j]=マス(i,j)における可能なポイントのリスト
dp=[[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(0)

for i in range(W+H-1):
  I,J=0,0
  if i < H:
    I=i
    J=0
  else:
    I=H-1
    J=i-H+1
  while I>=0 and J<W:
    sa = A[I][J] - B[I][J]
    for point in dp[I][J]:
      if I!=H-1:
        dp[I+1][J].add(point+sa)
        dp[I+1][J].add(abs(point-sa))
      if J!=W-1:
        dp[I][J+1].add(point+sa)
        dp[I][J+1].add(abs(point-sa))
    I-=1
    J+=1

ans=dp[H-1][W-1]
sa = A[H-1][W-1] - B[H-1][W-1]
res=float("inf")
for p in ans:
  res=min(res,abs(p+sa),abs(p-sa))
print(res)

### FIXED CODE ###

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

A=[list(map(int,input().split())) for _ in range(H)]
B=[list(map(int,input().split())) for _ in range(H)]

#dp[i][j]=マス(i,j)における可能なポイントのリスト
dp=[[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(0)

for i in range(W+H-1):
  I,J=0,0
  if i < H:
    I=i
    J=0
  else:
    I=H-1
    J=i-H+1
  while I>=0 and J<W:
    sa = abs(A[I][J] - B[I][J])
    for point in dp[I][J]:
      if I!=H-1:
        dp[I+1][J].add(point+sa)
        dp[I+1][J].add(abs(point-sa))
      if J!=W-1:
        dp[I][J+1].add(point+sa)
        dp[I][J+1].add(abs(point-sa))
    I-=1
    J+=1

ans=dp[H-1][W-1]
sa = abs(A[H-1][W-1] - B[H-1][W-1])
res=float("inf")
for p in ans:
  res=min(res,abs(p+sa),abs(p-sa))
print(res)
### BUGGY CODE ###

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

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0]*(n+1)

for i in range(n-1):
    ans[a[i]]+=1
ans.pop(0)
for j in ans:
    print(j)
### BUGGY CODE ###

import sys
import heapq

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
Q = []
for i in range(N):
    heapq.heappush(Q, (-B[i], i))
ans = 0
cnt = 0

while len(Q) != 0:
    _, i = heapq.heappop(Q)

    if (B[i] - A[i]) % (B[(i-1) % N] + B[(i+1) % N]) == 0:
        ans += (B[i] - A[i]) // (B[(i-1) % N] + B[(i+1) % N])
        cnt += 1
        B[i] = A[i]
    else:
        tmp = (B[i] - 1) // (B[(i-1) % N] + B[(i+1) % N])
        B[i] -= tmp * (B[(i-1) % N] + B[(i+1) % N])
        ans += tmp
        heapq.heappush(Q, (-B[i], i))
    
    if cnt == N:
        print(ans)
        sys.exit()

print(-1)

### FIXED CODE ###

import sys
import heapq

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
Q = []
for i in range(N):
    heapq.heappush(Q, (-B[i], i))
ans = 0
cnt = 0

while len(Q) != 0:
    _, i = heapq.heappop(Q)

    if (B[i] - A[i]) % (B[(i-1) % N] + B[(i+1) % N]) == 0:
        ans += (B[i] - A[i]) // (B[(i-1) % N] + B[(i+1) % N])
        cnt += 1
        B[i] = A[i]
    else:
        tmp = (B[i] - 1) // (B[(i-1) % N] + B[(i+1) % N])
        
        if tmp == 0:
            print(-1)
            sys.exit()
        
        B[i] -= tmp * (B[(i-1) % N] + B[(i+1) % N])
        ans += tmp
        heapq.heappush(Q, (-B[i], i))
    
    if cnt == N:
        print(ans)
        sys.exit()

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

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

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

max_n = 200000

ball_counts = [0]*max_n

for ball in balls:
    ball_counts[ball-1] += 1


counts = []

for n in ball_counts:
    if n !=0:
        counts.append(n)
        
counts = sorted(counts)

c = 0

while len(counts) > k:
    c += counts[0]
    del counts[0]

print(c)
    

### FIXED CODE ###

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

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

max_n = 200000

ball_counts = [0]*max_n

for ball in balls:
    ball_counts[ball-1] += 1


counts = []

for n in ball_counts:
    if n !=0:
        counts.append(n)
        
counts = sorted(counts)

print(sum(counts[0:len(counts)-k]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


def main():
    Q = int(input())
    is_prime, table = sieve(100000)
    N = []
    for p in table:
        if is_prime[(p+1)//2 - 1]:
            N.append(p)
    
    for _ in range(Q):
        l, r = map(int, input().split())
        cnt = 0
        for n in N:
            if l<=n and n<=r:
                cnt += 1
        print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


def main():
    Q = int(input())
    is_prime, table = sieve(100000)
    N = []
    for p in table:
        if is_prime[(p+1)//2 - 1]:
            N.append(p)
    
    for _ in range(Q):
        l, r = map(int, input().split())
        cnt = 0
        for n in N:
            if l<=n and n<=r:
                cnt += 1
        print(cnt)

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

# coding: utf-8

N, Q = map(int, input().split())
S = input()
l_r = [tuple(map(int, input().split())) for _ in range(Q)]

for l, r in l_r:
    print(S[l - 1:r].count("AC"))


### FIXED CODE ###

# coding: utf-8

N, Q = map(int, input().split())
S = input()
l_r = [tuple(map(int, input().split())) for _ in range(Q)]

isAC = [0] * N
cnt = 0
for i in range(len(S) - 1):
    if S[i] == "A" and S[i + 1] == "C":
        cnt += 1
    isAC[i + 1] = cnt

for l, r in l_r:
    print(isAC[r - 1] - isAC[l - 1])
### BUGGY CODE ###

n,m=map(int,input().split())
tenbo=[i for i in range(1,n+1)]
t=list(map(int,input().split()))
h=[0]+t
for i in range(m):
  a,b=map(int,input().split())
  if h[a]>=h[b] and b in tenbo:
    tenbo.remove(b)
  if h[a]<=h[b] and a in tenbo:
    tenbo.remove(a)
print(len(tenbo))

### FIXED CODE ###

n,m=map(int,input().split())
tenbo=[1 for i in range(n+1)]
t=list(map(int,input().split()))
h=[0]+t
tenbo[0]=0
for i in range(m):
  a,b=map(int,input().split())
  if h[a]>=h[b]:
    tenbo[b]=0
  if h[a]<=h[b]:
    tenbo[a]=0
print(sum(tenbo))
### BUGGY CODE ###

import math

N,K,*AF = map(int, open(0).read().split())
A = sorted(AF[:N])
F = sorted(AF[N:],reverse=True)
left = 0
right = max(A) * max(F)
while left != right:
    mid = (left+right) // 2
    if sum([max(A[i]-math.floor(mid/F[i]),0) for i in range(N)]) <= K:
        right = mid
    else:
        left = mid + 1
print(left)

### FIXED CODE ###

import math

N,K,*AF = map(int, open(0).read().split())
A = sorted(AF[:N])
F = sorted(AF[N:],reverse=True)
left = 0
right = max(A) * max(F)
while left != right:
    mid = (left+right) // 2
    temp = 0
    for i in range(N):
        temp += max(A[i]-math.floor(mid/F[i]),0)
        if temp > K:
            left = mid + 1
            break
    else:
        right = mid
print(left)
### BUGGY CODE ###

import math

k = int(input())
total = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            total += math.gcd(math.gcd(i, j),k)
print(total)

### FIXED CODE ###

import math

k = int(input())
total = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        tmp = math.gcd(i, j)
        for k in range(1,k+1):
            total += math.gcd(tmp,k)
print(total)
### BUGGY CODE ###

N,W= map(int,input().split())
w=[0]*N
v=[0]*N

for i in range(N):
  w[i],v[i]=map(int,input().split())
  
dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
  for j in range(0,W+1):
    if j<w[i-1]:
      dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=max( dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1] )
      
print(dp[N][W])

### FIXED CODE ###

N,W= map(int,input().split())
w=[0]*N
v=[0]*N

for i in range(N):
  w[i],v[i]=map(int,input().split())
  
dp=[[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1,N+1):
  for j in range(0,W+1):
    if j<w[i-1]:
      dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=max( dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1] )
      
print(dp[N][W])
### BUGGY CODE ###

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

tree = {}
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a] = tree.get(a, []) + [b]

op = {i: 0 for i in range(1, n+1)}
for i in range(q):
    p, x = map(int, input().split())
    op[p] = op[p] + x

for root in tree.keys():
    for i in tree[root]:
        op[i] += op[root]

print(*op.values())

### FIXED CODE ###

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

tree = [[] for i in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)

op = [0] * (n+1)
for i in range(q):
    p, x = map(int, input().split())
    op[p] += x

for root, reaf in enumerate(tree):
    for i in reaf:
        op[i] += op[root]

print(*op[1:])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = 0
while True:
    a = sorted(a)
    ec = 0
    for i in range(len(a)-1,-1,-1):
        if a[i]%2==0 and ec==0:
            a[i]/=2
            ec+=1
        elif a[i]%2==0:
            a[i]*=3
    if ec ==1:
        cnt+=1
    else:
        break        
print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(len(a)-1,-1,-1):
    if a[i]%2==0:
        while(a[i]%2==0):
            cnt+=1
            a[i]/=2
print(cnt)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
Alist = list(map(int,input().split()))
Blist = list(map(int,input().split()))
Clist = list(map(int,input().split()))

Alist.sort(reverse=True)
Blist.sort(reverse=True)
Clist.sort(reverse=True)

ABlist = []
for i in Alist[:k]:
    for j in Blist[:k]:
        ABlist.append(i + j)

ABlist.sort(reverse=True)

ABClist = []
for i in ABlist[:k]:
    for j in Clist[:k]:
        ABClist.append(i + j)

ABClist.sort(reverse=True)

for i in range(k):
    print(ABClist[i])


### FIXED CODE ###

x,y,z,k = map(int,input().split())
Alist = list(map(int,input().split()))
Blist = list(map(int,input().split()))
Clist = list(map(int,input().split()))

Alist.sort(reverse=True)
Blist.sort(reverse=True)
Clist.sort(reverse=True)

ABlist = [i + j for i in Alist[:k] for j in Blist[:k]]

ABlist.sort(reverse=True)

ABClist = [l + m for l in ABlist[:k] for m in Clist[:k]]

ABClist.sort(reverse=True)

print(*ABClist[:k], sep = '\n')
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
temp = [0]*n
count = 1
for i in range(1,n):
    temp = p[:i+1]
    if p[i] == min(temp):
        count += 1
print(count)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
count = 0
t = p[0]
for i in range(n):
    if p[i] <= t:
        count += 1
        t = p[i]
print(count)
### BUGGY CODE ###

N, M = map(int, input().split())
friend_list = [[0] * (N + 1) for _ in range(N + 1)]
number = [0] * (N + 1)
for _ in range(M):
    a, b = map(int, input().split())
    if friend_list[a][b] == 0:
        friend_list[a][b] = 1
        number[a] += 1
    if friend_list[b][a] == 0:
        friend_list[b][a] = 1
        number[b] += 1

ans = 0
ans = max(number)
print(ans + 1)

### FIXED CODE ###

from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

        if x == y:
            return

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

        self.par[y] = x
        self.size[x] += self.size[y]
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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


N, M = map(int, input().split())
uf = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a, b)

ans = max(uf.size)

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

n = int(input())
x = [int(i) for i in input().split()]
x_sorted = sorted(x)

x_1 = x_sorted[n // 2 - 1]
x_2 = x_sorted[n // 2]

for i in x:
    if x_sorted.index(i) < n // 2:
        print(x_2)
    else:
        print(x_1)

### FIXED CODE ###

n = int(input())
x = [int(i) for i in input().split()]
x_sorted = sorted(x)

x_1 = x_sorted[n // 2 - 1]
x_2 = x_sorted[n // 2]

for x_ in x:
    if x_ <= x_1:
        print(x_2)
    else:
        print(x_1)
### BUGGY CODE ###

Q = int(raw_input())
L, R = [], []
for i in range(Q):
	l_r = [int(num) for num in raw_input().split()]
	L.append(l_r[0])
	R.append(l_r[1])

max_num = max(R)
def decide_sosu(max_num):
	sosus = []
	for i in range(2, max_num + 1):
		flag = 0
		for num in sosus:
			if i % num == 0:
				flag = 1
				break
		if flag == 0:
			sosus.append(i)
	return sosus

sosus = decide_sosu(max_num+1)

c_s = [0] * (max_num + 1)
for i in range(2, max_num + 1):
	if (i in sosus) & (((i+1) % 2)==0) & ((i+1)/2 in sosus): 
		c_s[i] = c_s[i-1] + 1
	else:
		c_s[i] = c_s[i-1]

for i in range(Q):
	print c_s[R[i]] - c_s[L[i]-1]

### FIXED CODE ###

import math
Q = int(raw_input())
L, R = [], []
for i in range(Q):
	l_r = [int(num) for num in raw_input().split()]
	L.append(l_r[0])
	R.append(l_r[1])

max_num = max(R)
def calc_sosus(max_num):
	IsPrimes = [True] * (max_num + 1)
	IsPrimes[0] = False
	IsPrimes[1] = False
	for min_i in range(2, int(math.sqrt(max_num)) + 1):
		if IsPrimes[min_i]:
			for num in range(min_i*min_i, max_num+1, min_i):
				IsPrimes[num] = False
	return IsPrimes

IsPrimes = calc_sosus(max_num)

c_s = [0] * (max_num + 1)
for i in range(2, max_num + 1):
	if (IsPrimes[i]) & (((i+1) % 2)==0) & (IsPrimes[(i+1)/2]): 
		c_s[i] = c_s[i-1] + 1
	else:
		c_s[i] = c_s[i-1]

for i in range(Q):
	print c_s[R[i]] - c_s[L[i]-1]
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(1, n+1):
    idx = a.index(i)
    ans.append(idx+1)

for i in range(n):
    print(ans[i])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
dict_a = {}
for i in range(n):
    dict_a[i+1] = a[i]

dict_b = sorted(dict_a.items(), key=lambda x:x[1])

for i in range(n):
    print(dict_b[i][0])
### BUGGY CODE ###

a, b, x = map(int, input().split())
count = 0
for i in range(a,b+1):
    if i%x == 0:
        count += 1
print(count)

### FIXED CODE ###

a, b, x = map(int, input().split())
cnt = 0
if (a%x == 0):
    cnt+=1
cnt += b//x - a//x
print(cnt)
### BUGGY CODE ###

N, M = map(int, input().split())
a = list(int(input()) for i in range(M))
DP = [0]*(N+1)

for i in range(N+1):
    if i in a:
        DP[i] = 0
    elif i == 0 or i == 1:
        DP[i] = 1
    else:
        DP[i] = (DP[i-1]+DP[i-2])
print(DP[-1]%1000000007)

### FIXED CODE ###

#N = int(input())
N, M =  map(int,input().split())
#W =list(map(int,input().split()))
a = [(int(input())) for i in range(M)]

import sys

sys.setrecursionlimit(100000)
memo  =[-1]*(N+2)
def stair_count(n):
    if memo[n]!= -1:
        return memo[n]
    if n==0 or n==1:
        memo[n] =1
        return memo[n]
    memo[n] = stair_count(n-1) + stair_count(n-2)
    return memo[n]

start = 0
answer = 1
for i in a:
        if i == start:
            print(0)
            exit()
        else:
            n = i-1-start
            answer = (answer * stair_count(n))
            start = i+1
n = N -start
answer = (answer * stair_count(n))
print(answer%1000000007)
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
lst = list(map(int,input().split()))
x = sum(lst)%((10**9 + 7)*2)
y = x**2%((10**9 + 7)*2)
z = 0
for i in range(n):
    z = (z + (lst[i]%((10**9 + 7)*2))**2)%((10**9 + 7)*2)
ans = int((y - z)%((10**9 + 7)*2)/2)
print(ans)
### BUGGY CODE ###

n = int(input())
t = []
for _ in range(n):
    s = input()
    if not s in t:
        t.append(s)
    else:
        t.remove(s)
print(len(t))

### FIXED CODE ###

n = int(input())
t = [int(input()) for _ in range(n)]
t.sort()
c = 1
ans = 0
for i in range(1, n):
    if t[i - 1] == t[i]:
        c += 1
    else:
        if c % 2 != 0:
            ans += 1
        c = 1
if c % 2 != 0:
    ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

ans = 0
for i in range(60):
  count_one = sum(a>>i & 1 for a in A)
  ans += (count_one * (N - count_one) * (2 ** i) ) % MOD
  
    
print(ans%MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+ 7

ans = 0
two = 1
for i in range(61):
  n = len([ a for a in A if (a >> i) & 1 ])
  ans += (n * (N - n) * two % MOD)
  two *= 2 
print(ans%MOD)
### BUGGY CODE ###

from bisect import bisect_right as br
import heapq
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  if not A or A[0]>latest:
    pass
  else:
    for _ in range(br(A,latest)):
      A=A[1:]
      #index=br(works,B[0])
      #works=works[:index]+B[0]+works[index:]
      heapq.heappush(works,-B[0])
      B=B[1:]
  if not works:
    continue
  #ans+=works.pop(-1)
  ans-=heapq.heappop(works)

print(ans)


### FIXED CODE ###

import heapq
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort(reverse=True)
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[-1][0]<=latest:
    a,b=AB.pop()
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def inp():
    return int(input())
def inps():
    return input().rstrip()
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# import decimal
# from decimal import Decimal
# decimal.getcontext().prec = 10

# from heapq import heappush, heappop, heapify
# import math
# from math import gcd
# import itertools as it
# import collections
# from collections import deque 

# ---------------------------------------

N = inp()
S = inps()

r = []
g = []
b = []

for i in range(N):
    if S[i] == "R":
        r.append(i)
    if S[i] == "G":
        g.append(i)
    if S[i] == "B":
        b.append(i)

ans = 0
for i in r:
    for j in g:
        for k in b:
            if abs(i - j) != abs (j - k) and abs(i - j) != abs (i - k) and abs(i - k) != abs (j - k):
                ans += 1
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def inp():
    return int(input())
def inps():
    return input().rstrip()
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# import decimal
# from decimal import Decimal
# decimal.getcontext().prec = 10

# from heapq import heappush, heappop, heapify
# import math
# from math import gcd
# import itertools as it
# import collections
# from collections import deque 

# ---------------------------------------

N = inp()
S = inps()

r = []
g = []
b = []

for i in range(N):
    if S[i] == "R":
        r.append(i)
    if S[i] == "G":
        g.append(i)
    if S[i] == "B":
        b.append(i)

ans = 0
for i in r:
    for j in g:
        m = i
        n = j
        if m > n:
            m, n = n, m
        sa = abs(m - n)
        ans += len(b)
        if m - sa >= 0 and S[m - sa] == "B":
            ans -= 1
        if n + sa < N and S[n + sa] == "B":
            ans -= 1
        if sa % 2 == 0 and S[m + sa//2] == "B":
            ans -= 1
print(ans)