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

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

mem = [-1 for i in range(n+1)]
def countd(y):
  if mem[y] == -1:
    mem[y] = d.count(y)
  return mem[y]

if d[0] != 0:
  print(0)
  exit()

for i in range(n-1):
  x = d[i+1]
  if x == 0:
    print(0)
    exit()

count = 1
for i in range(n-1):
  count = count * countd(i) ** countd(i+1)
  count = count % 998244353

print(count)


### FIXED CODE ###

from collections import Counter

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

mem = Counter(d)

if d[0] != 0 or mem[0] != 1:
  print(0)
  exit()

count = 1
for i in range(max(d)):
  count = count * mem[i] ** mem[i+1]
  count = count % 998244353

print(count)
### BUGGY CODE ###

import itertools

n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
li=[i for i in range(1,n)]
ans=[]

for i in itertools.permutations(li, k-1):
  cost,height=0,A[0]
  for j in i:
    if height < A[j]:
      height=A[j]
      continue
    cost += (height-A[j]+1)
    height += 1 
  ans.append(cost)
  
print(min(ans))

### FIXED CODE ###

import itertools

n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
ans=[]

for li in itertools.product([0,1], repeat=n-1):
  if li.count(1) < k-1:
    continue
  cost,height=0,A[0]
  for i in range(1,n):
    if height < A[i]:
      height=A[i]
      continue
    if li[i-1]:
      cost += (height-A[i]+1)
      height += 1 
  ans.append(cost)
  
print(min(ans))
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
l = []
r = []
for i in range(q):
    li,ri = map(int,input().split())
    l.append(li)
    r.append(ri)
    
for i in range(q):
    print(s.count("AC",l[i]-1,r[i]))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
l = []
r = []
for i in range(q):
    li,ri = map(int,input().split())
    l.append(li)
    r.append(ri)
  
al = [0]*n
for i in range(1,n):
    if s[i-1] == "A" and s[i] == "C":
        al[i] = al[i-1] + 1
    else:
        al[i] = al[i-1]
        
for j in range(q):
    left = l[j]-1
    right = r[j]-1
    print(al[right]-al[left])
### BUGGY CODE ###

def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    A.sort()
    i = 1
    while i < len(A) - 1:
        if A[i+1][1]-A[i-1][1] < L :
            if A[i+1][0]==A[i-1][0] :
                del A[i]
                continue
        i += 1
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.997
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = A[j]
        for i,x in enumerate(ANS[a[1]:a[1]+L]):
            if x : continue
            else :
                ANS[a[1]+i] = a[0]
                D.add(a[1]+i)
                count += 1
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
if N != 10 ** 5 :
    ANS = SME()
    for i in ANS[L-1:-1]:print(i, end=" ")
    print(ANS[-1])
else :
    if max(Whole) < 10 ** 3 :
        ANS = SME()
        for i in ANS[L-1:-1]:print(i, end=" ")
        print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n, k = map(int, input().split())
s = list(input())
# print(n, k, s)

a = []
cnt = 0
for i in range(n-1):
    cnt += 1
    if s[i] != s[i+1]:
        a.append(cnt)
        cnt = 0 # reset
a.append(cnt+1)
# print(a) # 連続する0,1の数の配列を作った
### 前処理 両端が1の数を表す数列を作ることが出来た
if s[0] == "0": # 左端
    a.insert(0, 0)
if s[-1] == "0": # 右端
    a.append(0)
# print(a)
# print((len(a)-2*k+1)//2)
if (len(a)-2*k+1)/2 < 1:
    k = int((len(a)-1)/2)
# print(k)
ans = 0
for i in range((len(a)-2*k+1)//2):
    # b = 0
    b = sum(a[2*i:2*i+2*k+1])
    #for j in range(2*k+1):
    #    b += a[2*i+j]
    # print(i, b)
    ans = max(ans, b) # 最大値を更新していく
print(ans)


### FIXED CODE ###

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

# 累積和
a = [0]
if s[0] == "0":
	a.append(0)
for i in range(n):
	if i == n-1 or s[i+1] != s[i]:
		a.append(i+1) # 累積和

# print(s[-1])
if s[-1] == "0":
	a.append(a[-1])

if len(a) <= 2*k+1: # 2*k+1
	print(n)
else:
	ans = 0
	for j in range(0, len(a) - 2*k - 1, 2): # len(a)は奇数
		ans = max(ans, a[j+2*k+1] - a[j])
	print(ans)
### BUGGY CODE ###

def main():
    import sys
    N = int(input())
    left = 0
    right = N - 1
    table = ["?"]*N

    for i in range(21):
        c = (left + right) // 2
        if table[c] == "?":
            print(c)
            sys.stdin.flush()
            s = input()
            if s == "Vacant":
                return
            table[c] = s
        if table[left] == "?":
            print(left)
            sys.stdin.flush()
            le = input()
            if le == "Vacant":
                return
            table[left] = le
        if table[right] == "?":
            print(right)
            sys.stdin.flush()
            ri = input()
            if ri == "Vacant":
                return
            table[right] = ri
        if (ri - le) % 2 == 0 and table[left] != table[c]:
            right = c
        elif (ri - le) % 2 == 0 and table[right] != table[c]:
            left = c
        elif (ri - le) % 2 == 1 and table[left] == table[c]:
            right = c
        elif (ri - le) % 2 == 1 and table[right] == table[c]:
            left = c
        else:
            raise Exception


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    N = int(input())
    left = 0
    right = N
    table = ["?"]*N
    print(left)
    sys.stdin.flush()
    le = input()
    if le == "Vacant":
        return
    table[left] = le

    for i in range(20):
        c = (left + right) // 2
        print(c)
        sys.stdin.flush()
        s = input()
        if s == "Vacant":
            return
        table[c] = s
        if (c - left) % 2 == 0 and table[left] == table[c]:
            left = c
        elif (c - left) % 2 == 1 and table[left] != table[c]:
            left = c
        else:
            right = c


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

import numpy as np
R,C,K=map(int,input().split())
vl=np.zeros((R,C), np.int64)
for _ in range(K):
  r,c,v=map(int,input().split())
  vl[r-1][c-1]=v
dp=np.zeros((R+1,C+1,4), np.int64)
for i in range(1,R+1):
  for j in range(1,C+1):
    for k in range(4):
      dp[i][j][k]=max(dp[i][j-1][k],dp[i-1][j][3])
    for k in range(3,0,-1):
      dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+vl[i-1][j-1])
print(dp[R][C][3])

### FIXED CODE ###

import numpy as np
from numba import njit
R,C,K=map(int,input().split())
vl=np.zeros((R,C), np.int64)
for _ in range(K):
  r,c,v=map(int,input().split())
  vl[r-1][c-1]=v
@njit
def main():
  dp=np.zeros((R+1,C+1,4), np.int64)
  for i in range(1,R+1):
    for j in range(1,C+1):
      for k in range(4):
        dp[i][j][k]=max(dp[i][j-1][k],dp[i-1][j][3])
      for k in range(3,0,-1):
        dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-1]+vl[i-1][j-1])
  return dp[R][C][3]
print(main())
### BUGGY CODE ###

import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

import sys
from collections import defaultdict
input = sys.stdin.readline


N = int(input())

d2 = [1]
for _ in range(N):
    d2.append(2*d2[-1]%mod)

G = [[] for _ in range(N+1)]
for v in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += d2[f] - 1 % mod
xx = d2[N]
print((div(N, 2) - div(N+r, xx))%mod)


### FIXED CODE ###

import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

import sys
input = sys.stdin.readline


N = int(input())

d2 = [1]
inverse = [0, 1]
for _ in range(N):
    d2.append(2*d2[-1]%mod)
for i in range( 2,  10):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

G = [[] for _ in range(N+1)]
for v in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += d2[f] - 1 % mod
r = N*d2[N-1]-N-r
for _ in range(N):
    r = r*500000004 % mod
print(r)
### BUGGY CODE ###

from operator import itemgetter
N, M = map(int, input().split())
ab = []
for i in range(M):
    a,b = map(int, input().split())
    ab.append((a,b))
ab.sort(key=itemgetter(0))

fl = False
for i,j in ab:
    if i!=1:
        continue
    for k,l in ab:
        if i==1 and (j!=k or l!=N):
            continue
        else:
            fl = True
print('POSSIBLE') if fl else print('IMPOSSIBLE')

### FIXED CODE ###

from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(list)
for i in range(M):
    a,b = map(int, input().split())
    d[a].append(b)

for i,j in list(d.items()):
    if i!=1:
        continue
    for k in j:
        if N in d[k]:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')
### BUGGY CODE ###

# coding: utf-8

N, Q = [int(i) for i in input().split()]
S = input()
is_AC = [False] * N

for i in range(N):
  if S[i:i+2] == "AC":
    is_AC[i] = True

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


### FIXED CODE ###

# coding: utf-8
import sys
import numpy as np
input = sys.stdin.readline

N, Q = [int(i) for i in input().split()]
S = input()
is_AC = [False] * N
AC_csum = [0] * N
for i in range(N):
  is_AC[i] = S[i:i+2] == "AC"
  AC_csum[i] = AC_csum[i-1] + is_AC[i]

for i in range(Q):
  l, r = [int(i) for i in input().split()]
  ans = AC_csum[r-1] - AC_csum[l-1] - is_AC[r-1] + is_AC[l-1]
  print(ans)
### BUGGY CODE ###

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


DEBUG = True
dprint = print if DEBUG else lambda *x : x

H, N = [int(str) for str in input().strip().split()]
AB = [[int(str) for str in input().strip().split()] for _ in range(N)]

cosp = [i[0] / i[1] for i in AB]

bestshot = AB[cosp.index(max(cosp))]
rem = H % bestshot[0]

dp = [0]
for h in range(1, H + 1):
    dp.append(min([i[1] + dp[max(0, h - i[0])] for i in AB if AB[0]]))
    
print(dp[-1])

### FIXED CODE ###

H, N = [int(str) for str in input().strip().split()]
AB = [[int(str) for str in input().strip().split()] for _ in range(N)]

dp = [0]
for h in range(1, H + 1):
    a, b = min(AB, key=lambda i: i[1] + dp[max(0, h - i[0])])
    dp.append(b + dp[max(0, h - a)])    
print(dp[-1])
### BUGGY 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()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)            

ab=[]

for i in a:
    for j in b:
        ab.append(i+j)
ab.sort(reverse=True)
ab=ab[:k]
c=c[:k]
abc=[]
for i in ab:
    for j in c:
        abc.append(i+j)
abc.sort(reverse=True)

for i in abc[:k]:
    print(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()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = sorted(x+y for x in a for y in b)[:-k-1:-1]
abc = sorted(x+y for x in ab[:k] for y in c)[:-k-1:-1]
print(*abc, sep='\n')
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
import heapq

def cost(i,j):
    return abs(h[i] - h[j])

dp=[0]*n
dp[0]=0

for i in range(1,n):
    lst=[]

    for j in range(i-k,i):
        if j>=0:
            heapq.heappush(lst, dp[j]+cost(j,i))
    dp[i]=heapq.heappop(lst)

print(dp[n-1])

### FIXED CODE ###

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

def cost(i,j):
    return abs(h[i] - h[j])

dp=[10**9]*n
dp[0]=0

for i in range(1,n):
    for j in range(i-k,i):
        if j>=0:
            cst = dp[j]+cost(j,i)
            if dp[i] > cst:
                dp[i]=cst

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

import numpy as np
# Calculate intensity
N, K = [int(v) for v in input().split(" ")]
A_arr = np.array([int(v) for v in input().split(" ")])
step = np.arange(len(A_arr)) 
def Luminate(A_arr, i):
  isLuminated = np.abs(step - i) < A_arr
  return isLuminated

def get_Intensity(A_arr):
  return np.array([np.sum(Luminate(A_arr, i)) for i in range(len(A_arr))])

Intensity = A_arr
for i in range(K):
  Intensity = get_Intensity(Intensity+1)

print(" ".join([str(v) for v in Intensity]))


### FIXED CODE ###

import numpy as np
 
N, K = map(int, input().split(' '))
A = tuple(map(int, input().split(' ')))
indexes = np.arange(0, N)
 
dp = np.zeros(shape=N + 1, dtype=np.int64)
 
for k in range(K):
    np.add.at(dp, np.maximum(0, indexes - A), 1)
    np.add.at(dp, np.minimum(N, indexes + A + 1), -1)
    A = dp.cumsum()[:-1]
    if np.all(A == N):
        break
    dp *= 0
 
print(' '.join(map(str, A)))
### BUGGY CODE ###

N = int(input())
p = list(map(float, input().split()))

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
# dp[0][0] = 1-p[0]
# dp[0][1] = p[0]

for i in range(N):
    for j in range(i+1):
        # print(f"i {i}, j {j}")
        # print(f"p[i] {p[i]}, dp[i][j] {dp[i][j]}")

        if i == 0:
            dp[i+1][j] += 1-p[i]
            dp[i+1][j+1] += p[i]
        else:
            dp[i+1][j] += (1-p[i])*dp[i][j]
            dp[i+1][j+1] += p[i]*dp[i][j]
        # print("dp", dp)

ans = 0
for i, v in enumerate(dp[-1]):
    if i > N//2:
        ans += v

print(ans)

### FIXED CODE ###

N = int(input())
p = list(map(float, input().split()))

dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
# dp[0][0] = 1-p[0]
# dp[0][1] = p[0]

for i in range(N):
    for j in range(i+1):
        # print(f"i {i}, j {j}")
        # print(f"p[i] {p[i]}, dp[i][j] {dp[i][j]}")

        if i == 0:
            dp[i+1][j] += 1-p[i]
            dp[i+1][j+1] += p[i]
        else:
            dp[i+1][j] += (1-p[i])*dp[i][j]
            dp[i+1][j+1] += p[i]*dp[i][j]
        # print("dp", dp)

ans = 0
for i, v in enumerate(dp[-1]):
    if i > N//2:
        ans += v

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

N,M = map(int,input().split())
L=[]
for _ in range(N):
    a,b = map(int,input().split())
    L.append((a,b))
L.sort()
ans = 0
while M>0:
    a,b = L[0]
    del L[0]
    if M>=b:
        ans += a*b
    else:
        ans +=a*M
    M-=b
print(ans)

### FIXED CODE ###

import collections
N,M = map(int,input().split())
l=[]
for _ in range(N):
    a,b = map(int,input().split())
    l.append((a,b))
l.sort()
L = collections.deque(l)
ans = 0
while M>0:
    a,b = L.popleft()
    if M>=b:
        ans += a*b
    else:
        ans +=a*M
    M-=b
print(ans)
### BUGGY CODE ###

n = input()

remainder = [0]*2019
remainder[0] = 1

for i in range(len(n)):
	remainder[int(n[i:])%2019] += 1
    
res = 0
for e in remainder:
	res += e*(e-1)//2

print(res)

### FIXED CODE ###

n = input()

remainder = [0]*2019
remainder[0] += 1
x = 1
rem = 0

for i in range(1, len(n)+1):
	rem = (rem + int(n[-i])*x)%2019
	remainder[rem] += 1
	x *= 10
	x %= 2019
    
res = 0
for e in remainder:
	res += e*(e-1)//2

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

n, k = map(int, input().split())
a = tuple(map(int, input().split()))
 
point = 1
cnt = 1
m = 0
mm = 0
ind = 0
l = [1]
for i in range(n):
    point = a[point-1]
    cnt += 1
    if point in l:
        mm = i+1
        ind = l.index(point)
        m = cnt - 1 - ind
        break
    l.append(point)
 
if k >= mm:
    print(l[(k-mm)%m+ind])
else:
    print(l[k])

### FIXED CODE ###

from collections import deque

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

tere = {}
for i in range(n):
    tere[i+1] = a[i]

mati = deque([1])
mark = set([1])
tugi = 1
for i in range(1, k+1):
    if tere[tugi] not in mark:
        mati.append(tere[tugi])
        mark.add(tere[tugi])
    else:
        mati.append(tere[tugi])
        mark.add(tere[tugi])
        break
    tugi = tere[tugi]
else:
    print(tugi)
    exit()

mati = list(mati)
cnta = len(mati)-1
i = mati.index(mati[-1]) + 1
cntroop = cnta - i + 1
roop = mati[i:]

print(roop[(k-cnta)%cntroop-1])
### BUGGY CODE ###

def main():
    n = int(input())
    h = list(map(int, input().split()))
    max = 0
    now = 0
    i = 0
    while i < n - 1:
        now = 0
        for j in range(i + 1, n):
            if h[j] <= h[j - 1]:
                now += 1
                if j == n - 1:
                    if now >= max:
                        max = now
                    break
            else:
                if now >= max:
                    max = now
                i = j - 1
                break
        i += 1
    print(max)

if __name__ == "__main__":
    main()



### FIXED CODE ###

def main():
    n = int(input())
    h = input().split()
    h = [int(n) for n in h]
    max = 0
    now = 0
    i = 0
    for i in range(n-1):
        if h[i] >= h[i+1]:
            now += 1
        else:
            if now >= max:
                max = now
            now=0
        if now >= max:
            max = now
    print(max)

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

S = input()
N = len(S)
i = 0
T = ""
while i <= N-2:
    if S[i] == 'B' and S[i+1] == 'C':
        T += 'D'
        i += 1
    else:
        T += S[i]
    i += 1


N = len(T)
substring = []
l = 0
while l < N:

    if T[l] == 'B' or T[l] == 'C':
        l += 1
        continue
    
    r = l
    tmp = ''
    while r < N and (T[r] == 'A' or T[r] == 'D'):
        tmp += T[r]
        r += 1
    substring.append(tmp)
    if r == N:
        break
    else:
        l = r+1

ans = 0
for s in substring:
    M = len(s)
    D_count = [0]*(M+1)
    for i in range(M-1, -1, -1):
        D_count[i] = D_count[i+1]
        if s[i] == 'D':
            D_count[i] += 1
    
    for i in range(M):
        if tmp[i] == 'A':
            ans += D_count[i]

print(ans)





### FIXED CODE ###

S = input()
N = len(S)
i = 0
T = []
while i <= N-2:
    if S[i] == 'B' and S[i+1] == 'C':
        T.append('D')
        i += 1
    else:
        T.append(S[i])
    i += 1

T = "".join(T)

N = len(T)
ans = 0
l = 0
while l < N:

    if T[l] == 'B' or T[l] == 'C':
        l += 1
        continue
    
    r = l
    tmp = []
    while r < N and (T[r] == 'A' or T[r] == 'D'):
        tmp.append(T[r])
        r += 1
    
    M = len(tmp)
    D_count = [0]*(M+1)
    for i in range(M-1, -1, -1):
        D_count[i] = D_count[i+1]
        if tmp[i] == 'D':
            D_count[i] += 1
    
    for i in range(M):
        if tmp[i] == 'A':
            ans += D_count[i]
    
    if r == N:
        break
    else:
        l = r+1

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

from functools import lru_cache
import sys
input = sys.stdin.readline


@lru_cache(None)
def int_bitmap(n: int, size=32) -> tuple:
    table = [0] * size
    for i in range(size):
        table[i] = (n >> i) & 1
    return tuple(table)


@lru_cache(None)
def add_array(A: tuple, B: tuple) -> tuple:
    if len(A) != len(B):
        return tuple()
    else:
        return tuple([a + b for a, b in zip(A, B)])


@lru_cache(None)
def sub_array(A: tuple, B: tuple) -> tuple:
    if len(A) != len(B):
        return -1
    else:
        return tuple([a - b for a, b in zip(A, B)])


def bin_search(A, start, end):
    left, right = start, end
    while left < right:
        mid = (left + right) // 2
        if max(sub_array(A[end], A[mid])) < 2:  # midが条件を満たすとき、左をmidに置き換える
            right = mid
        elif max(sub_array(A[end], A[mid])) > 1:  # midを満たさないとき、左をmidに置き換える
            left = mid + 1
    return left


n = int(input())
_A = [int_bitmap(int(i), 20) for i in input().split()]

cusum = [None]
cusum[0] = int_bitmap(int(0), 20)

ans = 0

# pre-processsing for cul_sum
for i in range(1, n + 1):
    cusum.append(add_array(cusum[i - 1], _A[i - 1]))

for i in range(1, n + 1):

    if max(cusum[i]) < 2:
        ans += i
    # 右端をiとしたときに条件を満たす最長区間を２分探索する
    else:
        p = bin_search(cusum, 0, i)
        ans += (i - p)

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


n = int(input())
A = [int(i) for i in input().split()]
_sum = 0
_xor = 0
l, r = 0, 0
ans = 0
while l < n:
    while r < n and _sum + A[r] == _xor ^ A[r]:
        _sum += A[r]
        _xor ^= A[r]
        r += 1
    ans += r - l
    _sum -= A[l]
    _xor ^= A[l]
    if l == r:
        r += 1
    l += 1

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

N = int(input())
S = input()

L = []
flag1 = [0,1,2,3,4,5,6,7,8,9]
flag2 = [0,1,2,3,4,5,6,7,8,9]
flag3 = [0,1,2,3,4,5,6,7,8,9]

for i in range(N-2):
    x = int(S[i])
    if x in flag1:
        flag1[x] == 99999
    else:
        continue

    for j in range(i+1, N-1):
        y = int(S[j])
        if y in flag2:
            flag2[y] == 99999
        else:
            continue

        for k in range(j+1, N):
            z = int(S[k])
            if z in flag3:
                flag3[z] == 99999
            else:
                continue
            L.append(S[i] + S[j] + S[k])

print(len(set(L)))

### FIXED CODE ###

N = int(input())
S = list(map(int, list(input())))

cnt = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            pin = [i, j, k]
            x = 0

            for a in S:
                if a == pin[x]:
                    x += 1
                    if x == 3:
                        cnt += 1
                        break

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

N = int(input())

def f(n):
    cnt = 0
    e = int(n ** 0.5) + 1
    for x in range(1, e):
        for y in range(1, e):
            for z in range(1, e):
                if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == n:
                    cnt += 1

    return cnt

for i in range(1, N+1):
    print(f(i))


### FIXED CODE ###

n = int(input())

ans = [0 for _ in range(n+1)]

for x in range(1, int(n ** 0.5) + 1):
    for y in range(1, int(n ** 0.5) + 1):
        for z in range(1, int(n ** 0.5) + 1):
            a = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if a <= n:
                ans[a] += 1

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