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

import bisect
N = int(input())
*A, = map(int, input().split())
t = [[A[i], i] for i in range(N)]
t.sort()

ta = [v for v, i in t]
ti = [i for v, i in t]

ans = 0
for i in range(N):
    r = N-1-ta[i]
    ri = bisect.bisect_right(ta, r, lo=i+1)
    for j in range(i+1, ri):
        if (ta[i]+ta[j]) == abs(ti[i]-ti[j]):
            ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter

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

l = Counter([i-A[i] for i in range(N)])
r = Counter([i+A[i] for i in range(N)])

ans = 0
for k, v in l.items():
    ans += v*r[k]
print(ans)
### BUGGY CODE ###

import math
N, K = map(int, input().split())
lightPow = list(map(int, input().split()))

for i in range(K):
  newLightPow = [0]*N
  #print(lightPow)
  for pos in range(1, N+1):
    count = 0
    low = math.ceil(pos-(lightPow[pos-1]+0.5))
    high = math.floor(pos+(lightPow[pos-1]+0.5))
    low = min(max(1, low), N)
    high = min(max(1, high), N)
    for area in range(low, high+1):
      #print(area)
      newLightPow[area-1] += 1
    #print("pos:"+str(pos))
    #print("low"+str(low)+" high"+str(high))
    #print(newLightPow)
  lightPow = newLightPow
  
print(*lightPow)


### FIXED CODE ###

import math
N, K = map(int, input().split())
lightPow = list(map(int, input().split()))

for i in range(K):
  newLightPow = [0]*(N+1)
  #print(lightPow)
  for pos in range(1, N+1):
    low = pos - lightPow[pos-1]
    high = pos + lightPow[pos-1]
    low = min(max(1, low), N)
    high = min(max(1, high), N)
    newLightPow[low-1] += 1
    newLightPow[high] -= 1
    #print("pos:"+str(pos))
    #print("low"+str(low)+" high"+str(high))
    #print(newLightPow)
    
  check = True
  for i in range(0, N):
    if (i > 0):
      newLightPow[i] += newLightPow[i-1]
    if (newLightPow[i] < N):
      check = False
  lightPow = newLightPow
  if (check):
    break

print(*lightPow[:-1])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

for i in range(n):
  b = a[0:i]
  c = a[i+1:]
  b += c
  print(max(b))
  """
  # 遅すぎる
  b = a.copy()
  del b[i]
  print(max(b))
  """

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

# ほとんどは全体のmax?
m1 = max(a)

# max値が多い場合用に2nd max
m2 = sorted(a)[n-2]

for i in range(n):
  if a[i] == m1:
    print(m2)
  else:
    print(m1)
### BUGGY CODE ###

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

magic = []
for i in range(N):
    magic.append(tuple(map(int, input().split())))

INF = 10**15 
dp = [INF for _ in range(H+1)]
dp[0] = 0

for i, (a, b) in enumerate(magic):
    for h in range(H):
        dp[min(H, h+a)] = min(dp[min(H, h+a)], dp[h]+b)

print(dp[-1])

### FIXED CODE ###

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

magic = [list(map(int, input().split())) for _ in range(N)]

dp = [0 for _ in range(10**5)]

for i in range(H):
    dp[i] = min(dp[i-a]+b for a, b in magic)

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

N = int(input())
S = [input() for _ in range(N)]

for i in range(len(S)):
    a = sorted(S[i])
    S[i] = ''.join(a)

S_unq = set(S)
num_list = []

for i in S_unq:
    num = S.count(i)
    num_list.append(num)

dup_list = [i for i in num_list if i > 1]
dup_num = 0
for i in dup_list:
    b = (i * (i - 1)) / 2
    dup_num += b

print(int(dup_num))

### FIXED CODE ###

N = int(input())
strs = []
for i in range(N):
    s = list(input())
    s.sort()
    strs.append(''.join(s))

d = dict.fromkeys(strs, 0)
for s in strs:
    if s in d.keys():
        d[s] += 1
    else:
        d.setdefault(s, 1)

ans = 0
for v in d.values():
    ans += (v * (v - 1)) / 2

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

import math
a,b,x = map(int, input().split())
def f(a,b,t):
  if t < math.atan(a/b): return a*a*b - a*a*a*math.tan(t)/2
  elif t > math.atan(a/b): return a*b*b*math.tan(math.pi/2-t)/2
  else: return a*a*b/2
  
th = [math.atan(a/b), 0, math.pi/2]
err = float("inf")
eps = 1e-6
while abs(err) > eps:
  err = x - f(a,b,th[0])
  if abs(err) < eps: break
  elif err < 0:
    th[0], th[1] = (th[2]-th[0])/2+th[0], th[0]
  elif err > 0:
    th[0], th[2] = (th[0]-th[1])/2+th[1], th[0]
    
  #print(err, th)
print(math.degrees(th[0]))

### FIXED CODE ###

from math import tan, pi
a,b,x = map(int, input().split())
eps = 1e-6

def f(a,b,t):
  if pi/2-t<eps: return 0
  if b*tan(pi/2.-t) < a: return b*b*tan(pi/2.-t)/2.*a
  else: return a*a*b - a*a*tan(t)/2.*a
  
th_p, th_n = pi/2, 0.
for i in range(100000):
  th_m = (th_p + th_n)/2.
  err = f(a,b,th_m) - x
  if err**2 < eps**2: break
  elif err < 0: th_p = th_m
  else: th_n = th_m
print(180/pi*th_m)
### BUGGY CODE ###

N , T = map(int,input().split(' '))
AB = []
for _ in range(N):
    AB.append(list(map(int,input().split())))
dp = [-1] * (T+3000)
dp[0] = 0
for a,b in sorted(AB):
    for i in range(T-1,-1,-1):
        if dp[i] == -1:
            continue
        if dp[i+a] < dp[i] + b:
            dp[i+a] = dp[i] +b 
print(max(dp))

### FIXED CODE ###

import numpy as np
 
N, T = map(int, input().split())
data = []
for i in range(N):
  a, b = map(int, input().split())
  data.append((a,b))
data.sort()
data = np.array(data)

dp = np.zeros(T)
ans = 0
for a, b in data:
    ans = max(ans,dp[-1]+b)
    if a< T:
        newtable = dp[:T-a] + b
        dp[a:] = np.maximum(dp[a:], newtable)

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

import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    black = []
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                black.append((h, w))

    ans = 0
    for sh, sw in black:
        visited = [[0] * W for _ in range(H)]
        q = deque([("#", sh, sw)])

        while q:
            s, h, w = q.popleft()

            for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nh = h + dh
                nw = w + dw
                if 0 <= nh < H and 0 <= nw < W:
                    if visited[nh][nw] == 0:
                        if s == S[nh][nw]:
                            continue
                        else:
                            if S[nh][nw] == ".":
                                ans += 1
                            visited[nh][nw] = 1
                            q.append((S[nh][nw], nh, nw))

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    seen = [[False] * W for _ in range(H)]

    def dfs(sh, sw):
        q = deque([(sh, sw)])
        seen[sh][sw] = True
        black = 0
        white = 0
        if S[sh][sw] == "#":
            black += 1
        else:
            white += 1

        while q:
            h, w = q.popleft()

            for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nh = h + dh
                nw = w + dw

                if 0 <= nh < H and 0 <= nw < W:
                    if seen[nh][nw]:
                        continue
                    if S[h][w] == S[nh][nw]:
                        continue

                    seen[nh][nw] = True
                    q.append((nh, nw))
                    if S[nh][nw] == "#":
                        black += 1
                    else:
                        white += 1

        return black * white

    ans = 0
    for h in range(H):
        for w in range(W):
            if seen[h][w]:
                continue
            ans += dfs(h, w)

    print(ans)


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

Q = int(input())
queries = []
for _ in range(Q):
    queries.append(input())

from bisect import insort_left

ary, asum, bsum, c = [], 0, 0, 0
for query in queries:
    if query[0] == '2':
        absum = sum(abs(a - ary[(c-1)//2]) for a in ary)
        # absum = asum - (c//2 + 1) * ary[(c-1)//2]
        print(' '.join(map(str, (ary[(c-1)//2], absum + bsum))))
    else:
        _, a, b = map(int, query.split())
        insort_left(ary, a)
        # asum += a
        bsum += b
        c += 1


### FIXED CODE ###

Q = int(input())
INF = 10 ** 9

queries = []
for _ in range(Q):
    queries.append(input())

from bisect import insort_left
from heapq import heappush, heappop

absum, bsum, c = 0, 0, 0
# left, right = -INF, INF
lefts, rights = [INF], [INF]
for query in queries:
    if query[0] == '2':
        # absum = sum(abs(a - ary[(c-1)//2]) for a in ary)
        # absum = asum - (c//2 + 1) * ary[(c-1)//2]
        # print(' '.join(map(str, (ary[(c-1)//2], absum + bsum))))
        # print(str(ary[(c-1)//2]) + ' ' + str(absum + bsum))
        print(-lefts[0], absum + bsum)
    else:
        _, a, b = map(int, query.split())
        if c % 2 == 0:
            if -lefts[0] <= a <= rights[0]:
                heappush(lefts, -a)
                heappush(rights, a)
                absum += 0
            elif a < -lefts[0]:
                heappush(lefts, -a)
                heappush(rights, -lefts[0])
                absum += -lefts[0] - a
            else:
                heappush(rights, a)
                heappush(lefts, -rights[0])
                absum += a - rights[0]
        else:
            if a < -lefts[0]:
                absum += -lefts[0] - a
                heappop(lefts)
                heappush(lefts, -a)
            else:
                absum += a - rights[0]
                heappop(rights)
                heappush(rights, a)
        # left, right = ary[(c-1)//2], ary[c - (c-1)//2 - 1]        
        bsum += b
        c += 1
### BUGGY CODE ###

INF=10**18
def calc(a,b,xor):
  if (a&1)^(b&1)!=(xor&1):
    return INF
  if xor==0:
    if a<b:
      return INF
    else:
      return (a-b)//2
  x=2*calc(a//2,b//2,xor//2)
  y=2*calc((a-1)//2,(b+1)//2,xor//2)+1
  return min(x,y)

n=int(input())
arr=list(map(int,input().split()))
a,b=arr[0],arr[1]
xor=0
for i in range(2,n):
  xor^=arr[i]
ans=calc(a,b,xor)
if ans>=a:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

INF=10**18
def calc(a,b,xor):
  if (a,b,xor) in memo:
    return memo[(a,b,xor)]
  if (a&1)^(b&1)!=(xor&1):
    return INF
  if xor==0:
    if a<b:
      return INF
    else:
      return (a-b)//2
  x=2*calc(a//2,b//2,xor//2)
  y=2*calc((a-1)//2,(b+1)//2,xor//2)+1
  memo[(a,b,xor)]=min(x,y)
  return memo[(a,b,xor)]

n=int(input())
arr=list(map(int,input().split()))
a,b=arr[0],arr[1]
xor=0
for i in range(2,n):
  xor^=arr[i]
memo={}
ans=calc(a,b,xor)
if ans>=a:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

N,M = [int(i) for i in input().split()]
ans = [0]*N
for _ in range(M):
    L,R = [int(i)-1 for i in input().split()]
    for j in range(L,R+1):
        ans[j] += 1

count = 0
for i in ans:
    if i == M:
        count += 1

print(count)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M = [int(i) for i in input().split()]
L_max = 0
R_min = 10**9
for _ in range(M):
    L,R = [int(i) for i in input().split()]
    L_max = max(L_max,L)
    R_min = min(R_min,R)

if R_min-L_max+1 > 0:
    print(R_min-L_max+1)
else:
    print(0)
### BUGGY CODE ###

n = int(input())
ans = 0
c = 1
for i in range((n%2)+2,n+1,2):
    c *= i
    S = str(c)
    j = 0
    for s in S[::-1]:
        if s == '0':
            ans += 1
            j += 1
        else:
            break
    if j:
        c = int(S[0:-j])
    else:
        c = int(S)
print(ans)

### FIXED CODE ###

n = int(input())
if n%2 == 1:
    print(0)
else:
    ans = 0
    i = 10
    while i <= n:
        ans += n//i
        i *= 5
    print(ans)
### BUGGY CODE ###

n = int(input())
s = str(input())
ans = s.count('#')
for i in range(n):
    w = s[:i].count('#')
    b = s[i:].count('.')
    ans = min(ans, w + b)
print(ans)


### FIXED CODE ###

n = int(input())
s = str(input())
ans = s.count('.')
L = [[0, s.count('.')]]
for i in range(n):
    if s[i] == '#':
        L.append([L[i][0]+1, L[i][1]])
    else:
        L.append([L[i][0], L[i][1]-1])
    ans = min(ans, L[-1][0] + L[-1][1])
print(ans)
### BUGGY CODE ###

n=int(input())
s=[input() for _ in range(n)]
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        if sorted(s[i])==sorted(s[j]):
            ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s = [input() for _ in range(n)]

dic={}

for i in  s:
    i = sorted(i)
    i = ''.join(i)
    if i in dic:
        dic[i]+=1
    else:
        dic[i]=1

ans =0
for i in dic.values():
    if i==1:
        continue
    else:
        ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        k=j+1
        while k<n:
            if l[i]+l[j]>l[k]:
                k+=1
                ans+=1
            else:
                break
print(ans)


### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
p.sort()
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        if j<n-2:
            l=j+1
            r=n-1
            while r-l>1:
                c=(l+r)//2
                if p[c]>=p[i]+p[j]:
                    r=c
                else:
                    l=c
            if p[l]<p[i]+p[j]:
                ans+=l-j
            if p[r]<p[i]+p[j]:
                ans+=1
        if j==n-2:
            if p[i]+p[n-2]>p[n-1]:
                ans+=1
print(ans)
### BUGGY CODE ###

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

for i in range(n):
    if i == 0:
        l.append(a[0])
    else:
        if max(l) <= a[i]:
            l.append(a[i])
        else:
            l.append(max(l))
            
print(sum(l) - sum(a))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
l = [a[0]]

for i in range(n-1):
    if l[i] >= a[i+1]:
        l.append(l[i])
    else:
        l.append(a[i+1])

print(sum(l) -sum(a))
### BUGGY CODE ###

N, X, Y = map(int, input().split(' '))

dct = {X : Y}
short = Y - X - 1

dist_list = []

for i in range(1,N):
    for j in range(i+1,N+1):
        if i <= X and j >= Y:
            dist = j - i - short
        elif i <= X and j >= X and j <= Y:
            d1 = X - i + 1 + Y - j
            d2 = j - i
            dist = min(d1,d2)
        elif i >= X and i <= Y and j >= Y:
            d1 = i - X + 1 + j - Y
            d2 = j - i
            dist = min(d1,d2)
        elif i >= X and j <= Y:
            d1 = i - X + 1 + Y - j 
            d2 = j - i
            dist = min(d1,d2)
        else:
            dist = j - i
        dist_list.append(dist)

for k in range(1,N):
    print(dist_list.count(k))

### FIXED CODE ###

N, X, Y = map(int, input().split(' '))

dist_list = [0] * N

for i in range(1,N):
    for j in range(i+1,N+1):
        d1 = abs(X - i) + 1 + abs(Y - j)
        d2 = j - i
        dist = min(d1,d2)
        dist_list[dist] += 1

for k in range(1,N):
    print(dist_list[k])
### 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()))
re=[0]*n
for i in a:
  re[i-1]+=1
for i in re:
  print(i)
### BUGGY CODE ###

s = input()
n = int(input())
q = []
for i in range(n):
  query = list(input().split())
  q.append(query)
for i in range(n):
  if int(q[i][0]) == 1:
    s = s[::-1]
  else:
    if int(q[i][1]) == 2:
      s = s + q[i][2]
    else:
      s = q[i][2] + s
print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
n = int(input())
q = []
for i in range(n):
  query = list(input().split())
  q.append(query)
  
a = 1
for i in range(n):
  if int(q[i][0]) == 1:
    a *= -1
  else:
    if int(q[i][1]) == 1:
      if a > 0:
        s.appendleft(q[i][2])
      else:
        s.append(q[i][2])
    else:
      if a > 0:
        s.append(q[i][2])
      else:
        s.appendleft(q[i][2])
s = list(s)
s = "".join(s)
if a > 0:
  print(s)
else:
  s = s[::-1]
  print(s)
### BUGGY CODE ###

S = input()
nQ_r = S.count('?')
nC_r = S.count('C')
nQ_l = 0
nA_l = 0
N = len(S)
mod = 10**9+7
ans = 0
for n, c in enumerate(S):
    if c=='C': nC_r-=1
    if c=='?': nQ_r-=1
    
    if n>0 and n<N-1 and (c=='B' or c=='?'):
        p = ( nQ_l*(3**max(0, nQ_l-1) % mod) + nA_l*(3**nQ_l % mod) ) % mod
        q = ( nQ_r*(3**max(0, nQ_r-1) % mod) + nC_r*(3**nQ_r % mod) ) % mod
        ans += p * q
        ans %= mod

    if c=='A': nA_l+=1
    if c=='?': nQ_l+=1

print(ans)

### FIXED CODE ###

S = input()
nQ_r = S.count('?')
nC_r = S.count('C')
nQ_l = 0
nA_l = 0
N = len(S)
mod = 10**9+7

pow3 = [1]*N
p = 1
for i in range(1,N):
    pow3[i] = p = p*3%mod

ans = 0
for n, c in enumerate(S):
    if c=='C': nC_r-=1
    if c=='?': nQ_r-=1
    
    if n>0 and n<N-1 and (c=='B' or c=='?'):
        p = ( nQ_l*pow3[max(0, nQ_l-1)] + nA_l*pow3[nQ_l] ) % mod
        q = ( nQ_r*pow3[max(0, nQ_r-1)] + nC_r*pow3[nQ_r] ) % mod
        ans += p * q
        ans %= mod

    if c=='A': nA_l+=1
    if c=='?': nQ_l+=1

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

n = int(input())
a = list(int(input()) for i in range(n))
t = []
o = 1

while o != 2:
    if o in t:
        print(-1)
        exit(0)
    t.append(o)
    o = a[o-1]

print(len(t))

### FIXED CODE ###

n = int(input())
a = list(int(input()) for i in range(n))
t = []
o = 1

while o != 2:
    if len(t) > n:
        print(-1)
        exit(0)
    t.append(o)
    o = a[o-1]

print(len(t))
### BUGGY CODE ###

from math import factorial
from collections import Counter
mod = 10**9 + 7

n = int(input())
length = n+1
li = list(map(int,input().split()))

counter = Counter(li)
dup = counter.most_common()[0][0]
be, af = [i for i, x in enumerate(li) if x==dup]
soto = be + length - af - 1

for k in range(1, n+2):
    if k == 1:
        print(n)
    elif k == n+1:
        print(1)
    else:
        zyouhukuari = factorial(length) // (factorial(k)*factorial(length-k))
        if soto-k+1 >= 0:
            zyouhuku = factorial(soto) // (factorial(k-1)*factorial(soto-k+1))
        else:
            zyouhuku = 0
        val = zyouhukuari - zyouhuku
        print(val%mod)

### FIXED CODE ###

import collections

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

c = collections.Counter(a)
dup = c.most_common()[0][0]

id = [i for i, x in enumerate(a) if x == dup]
L = id[0]
R = id[1]

MOD = 10**9 +7
factorial = [1]
inverse = [1]

for i in range(1, N+2):
    factorial.append(factorial[i-1] * i % MOD)
    inverse.append(pow(factorial[i], MOD-2, MOD))
    

def C(n, r):
    if n < r:
        return 0
    return (factorial[n] * inverse[r] * inverse[n-r]) % MOD

print(N)
for i in range(2, N+2):
    ans = (C(N+1, i) - C(L+(N-R), i-1)) % MOD
    print(ans)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()

def b_search(L,key,left,right,slice):
    #L[i] < keyを満たす最大のi
    #L[i] < key <= L[i+1]
    if key <= L[left]:
        return 0
    elif key > L[len(L)-1]:
        return len(L) - slice
    else:
        mid = (left+right)//2
        if L[mid] < key and key <= L[mid+1]:
            return mid+1-slice
        elif L[mid] >= key:
            return b_search(L,key,left,mid,slice)
        else:
            return b_search(L,key,mid,right,slice)

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ans += b_search(L,L[i]+L[j],j+1,len(L),j+1)
print(ans)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        ans += bisect_left(L,L[i]+L[j])-(j+1)
print(ans)
### BUGGY CODE ###

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

dic = {}
for i in range(n):
  if an[i] not in dic.keys():
    dic[an[i]] = 1
  else:
    dic[an[i]] += 1

for i in range(n):
  sum = 0
  for k,v in dic.items():
    if an[i] == k:
      sum += (v-1)*(v-2)//2
    else:
      sum += v*(v-1)//2
  print(sum)

### FIXED CODE ###

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

dic = {}
for i in range(n):
  if an[i] not in dic.keys():
    dic[an[i]] = 1
  else:
    dic[an[i]] += 1

ans = {}
all_pattern = 0
for k,v in dic.items():
    if v >= 2:
        all_pattern += v*(v-1)//2
for k,v in dic.items():
    ans[k] = all_pattern - (v-1)
for v in an:
    print(ans[v])
### BUGGY CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = sorted(list(set(a)))
prime_bool = [True]*(max(a)+1)
prime_bool[0] = False

for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    #print(p)
    for j in range(2*p, max(a)+1, p):
      prime_bool[j] = False

count = 0
for i in range(len(prime_bool)):
  if prime_bool[i]:
    if c[i] == 1:
      count += 1
print(count)
#print(prime_bool)


### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = sorted(list(set(a)))
max_ = max(a)+1
prime_bool = [True]*max_
prime_bool[0] = False

for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    #print(p)
    k = 2
    while k*p < max_:
      prime_bool[k*p] = False
      k += 1

count = 0
for i in range(len(prime_bool)):
  if prime_bool[i]:
    if c[i] == 1:
      count += 1
print(count)
#print(prime_bool)
### BUGGY CODE ###

q = int(input())
l_lst = []
r_lst = []
for i in range(q):
  l, r = map(int, input().split())
  l_lst.append(l)
  r_lst.append(r)
max_ = max(r_lst)

primes = [2]
for L in range(3, max_+1, 2):
    for L2 in primes:
        if L % L2 == 0:
            break
    else:
        primes.append(L)
        
for l, r in zip(l_lst, r_lst):
  cnt = 0
  for j in range(l, r+1):
    if j in primes and (j+1)//2 in primes:
      cnt += 1
  print(cnt)
      


### FIXED CODE ###

flag = [False]*100001
c = [0]*100002
n = int(input())

for i in range(2,100000):
    if(not(flag[i])):
        for j in range(i+i,100000,i):
            flag[j] = True

for i in range(3,100000,2):
    if(not(flag[i]) and not(flag[(i+1)//2])):
        c[i]+=1
for i in range(3,100000):
    c[i]+=c[i-1]

while(n):
    n-=1
    l,r = map(int,input().split())
    print(c[r]-c[l-1])
### BUGGY CODE ###

N=input()
A=[int(x)for x in input().split()]
B=[0]
for x in A:
	B.append(B[-1]+x) 
count=0

for i in range(len(B)-1,-1,-1):
  for j in range(i-1,-1,-1):
    if B[i]==B[j]:
      count+=1
print(count)

### FIXED CODE ###

import collections
N=input()
A=[int(x)for x in input().split()]
B=[0]
count=0
for x in A:
  i=B[-1]+x
  B.append(i)

dic=collections.Counter(B)
for key,c in dic.items():
  count+=c*(c-1)//2
print(count)
### BUGGY CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

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

    # dp[j] := 表が j 枚となる確率
    # dp[j] = dp[j-1]*p[i] + dp[j]*(1-p[i])
    dp = [0.0] * (N+1)
    # 初期条件
    dp[0]= 1.0

    for i in range(N):
        # 更新前のdpを更新に使う。
        dp_before_update = dp[:]
        for j in range(N+1):
            dp[j] = (dp_before_update[j-1] * lst_p[i]) + (dp_before_update[j] * (1 - lst_p[i]))
    
    ans = sum(dp[(N//2+1):])

    print(ans)

main()

### FIXED CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

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

    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # 次のコインが表: dp[i+1][j+1] += dp[i][j]∗p[i]
    # 次のコインが裏: dp[i+1][j] += dp[i][j]∗(1.0−p[i])
    dp = [[0] * (N+1) for i in range(N+1)]

    # 初期条件
    dp[0][0] = 1.0

    for i in range(N):
        for j in range(N):
            dp[i+1][j+1] += dp[i][j] * lst_p[i]
            dp[i+1][j] += dp[i][j] * (1.0 - lst_p[i])
    
    ans = 0
    for i in range((N+1)//2, N+1):
        ans += dp[N][i]

    print(ans)

main()
### BUGGY CODE ###

S = input()
s = list(S)
num_list = [s[:i].count("B") if s[i] == "W" else 0 for i in range(1, len(s))]
print(str(sum(num_list)))


### FIXED CODE ###

s = list("BWBWBW" * 10000)

s = list(input())
ret, counter = 0, 0
for a in s:
    if a == "B":
        counter += 1
    else:
        ret += counter
print(str(ret))