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

n = input()
b = []
b_old = []
for i in range(int(n)):
    tmp = input()
    b.append(int(tmp))

count = 1
s = b[0]
if s == 2:
    print(count)
else:
    b_old.append(s)
    n_b = s
    flag = 0
    while(True):
        count += 1
        n_b = b[n_b-1]
        if n_b == 2:
            print(count)
            flag = 1
            break
        elif n_b in b_old:
            print("-1")
            flag = 1
            break
        elif count == int(n):
            print("-1")
            break
        else:
            b_old.append(n_b)


### FIXED CODE ###

n = int(input())
b = []
b_old = []
for i in range(n):
    tmp = int(input())
    b.append(tmp)
n_b = 1
count = 0
flag = 0
while(count < n):
    n_b = b[n_b-1]
    count += 1
    if n_b == 2:
        print(count)
        flag = 1
        break
if flag == 0:
    print("-1")
### BUGGY CODE ###

A, B, K = map(int, input().split())
for i in range(A, B+1):
    if i < (A+K) or i > (B-K):
        print(i)

### FIXED CODE ###

A, B, K = map(int, input().split())
list=[]
for i in range(A, A+K):
    if i < A+K and i <= B:
        list.append(i)
for i in range(B-K, B+1):
    if i > (B-K) and i >= A:
        list.append(i)
for i in sorted(set(list)):
    print(i)
### BUGGY CODE ###

n,k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
inf = 10**10
dp = [inf]*n
dp[0] = 0

for i in range(1,n):
    dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]) for j in range(min(i,k)+1))

print(dp[n-1])

### FIXED CODE ###

n,k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
inf = 10**10
dp = [inf]*n
dp[0] = 0
 
for i in range(1,n):
    dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]) for j in range(min(i,k)+1))
 
print(dp[n-1])
### BUGGY CODE ###

N, K = [int(n) for n in input().split()]

Heights = [int(n) for n in input().split()]
Costs = [float('inf') for n in range(N)]

for i in range(N):
    if i == 0:
        Costs[i] = 0
    elif i < K:
        for j in range(i+1):
            Costs[i] = min(Costs[i], Costs[i-j] + abs(Heights[i] - Heights[i-j]))
    else:
        #Costs[i] = min(Costs[i-1] + abs(Heights[i] - Heights[i-1]), Costs[i-2] + abs(Heights[i] - Heights[i-2]))
        for j in range(K+1):
            Costs[i] = min(Costs[i], Costs[i-j] + abs(Heights[i] - Heights[i-j]))

print(Costs[-1])


### FIXED CODE ###

N, K = [int(n) for n in input().split()]

Heights = [int(n) for n in input().split()]
Costs = [float('inf') for n in range(N)]

for i in range(N):
    if i == 0:
        Costs[i] = 0
    elif i < K:
        for j in range(i+1):
            Costs[i] = min(Costs[i], Costs[i-j] + abs(Heights[i] - Heights[i-j]))
    else:
        #Costs[i] = min(Costs[i-1] + abs(Heights[i] - Heights[i-1]), Costs[i-2] + abs(Heights[i] - Heights[i-2]))
        for j in range(K+1):
            Costs[i] = min(Costs[i], Costs[i-j] + abs(Heights[i] - Heights[i-j]))

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

k=int(input())
num=100
ans=0
while k!=num:
    num=num*101//100
    ans+=1
print(ans)

### FIXED CODE ###

from decimal import Decimal
k=int(input())
num=100
ans=0
while k>num:
    num=int(Decimal(num)*Decimal(101)/Decimal(100))
    ans+=1
print(ans)
### BUGGY CODE ###

from math import sqrt
cash = {}
def isprime(n):
    if n in cash:
        return cash[n]
    if n == 1:
        cash[n] = 0
        return 0
    if n == 2:
        cash[n] = 1
        return 1
    if n % 2 == 0:
        cash[n] = 0
        return 0
    for i in range(3,int(sqrt(n)+1))[0::2]:
        if n % i == 0:
            cash[n] = 0
            return 0
    cash[n] = 1
    return 1

from sys import stdin
cash2 = {}
for i in stdin:
    i = int(i)
    c = sum(isprime(n) for n in range(2,i+1))
    print(c)

### FIXED CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n)
    if n % 2 == 0:
      l = [0, 1] + [1, 0] * (int(n/2) - 1)
    else:
      l = [0, 1] + [1, 0] * (int(n/2) - 1) + [1]
    c = 3
    while c < mx:
        for k in range(c*2, n+1, c):
            l[k-1] = 0
        c = l[(c+1):].index(1) + c +2
        while c % 2 == 0:
            c = l[(c+1):].index(1) + c +2
    return l
t = cntPrime(1000000)
for n in stdin:
    n = int(n)
    print(sum(t[:n]))
### BUGGY CODE ###

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

a = list(map(int,input().split()))
bclist = [list(map(int,input().split())) for _ in range(m)]

all = a

for bc in bclist:
    for i in range(bc[0]):
        all.append(bc[1])

all.sort()

print(sum(all[(len(all)-n):]))

### FIXED CODE ###

n,m = map(int, input().split())
a = list(map(int,input().split()))
bclist = [list(map(int,input().split())) for _ in range(m)]

bclist=sorted(bclist, key = lambda x:x[1], reverse=True)

all = []


for i in range(m):
    all.extend([bclist[i][1]]*bclist[i][0])
    if len(all) >n:
        break

all.extend(a)
all.sort(reverse=True)

print(sum(all[:n]))
### BUGGY CODE ###

N = int(input())
d = list(map(int, input().split()))
""" 
d = [9, 1, 4, 4, 6, 7]
#N = 8
N = 6
#d = [9, 1, 14, 5, 5, 4, 4, 14]
d = [9, 1, 4, 4, 6, 7]
 """
# prob
# [number,value]
prob = []
cnt = 0
for i in d:
    prob.append([cnt, i])
    cnt += 1

""" print(prob)
print(sorted(prob, key=lambda x: x[1]))
 """
sorted_d = sorted(prob, key=lambda x: x[1])

d_max = sorted_d[N-1][1]
d_min = sorted_d[0][1]
#print(d_min, d_max)

cnt = 0
for i in range(N):
    """ print(sorted_d[0:i])
    print(sorted_d[i:])
 """
    if len(sorted_d[0:i]) == len(sorted_d[i:]):
        """ print("True")
        print(sorted_d[i][1])
        print(sorted_d[i-1][1])
        print(sorted_d[i][1] - sorted_d[i-1][1])
         """
        cnt += sorted_d[i][1] - sorted_d[i-1][1]
    # print("------")

print(cnt)


### FIXED CODE ###

N = int(input())
d = list(map(int, input().split()))
""" 
d = [9, 1, 4, 4, 6, 7]
#N = 8
N = 6
#d = [9, 1, 14, 5, 5, 4, 4, 14]
d = [9, 1, 4, 4, 6, 7]
 """
# prob
# [number,value]
prob = []
cnt = 0
for i in d:
    prob.append([cnt, i])
    cnt += 1

""" print(prob)
print(sorted(prob, key=lambda x: x[1]))
 """
sorted_d = sorted(prob, key=lambda x: x[1])

#print(d_min, d_max)
cnt = 0
# if len(sorted_d[0:i]) == len(sorted_d[i:]):
cnt += sorted_d[int(N/2)][1] - sorted_d[int(N/2-1)][1]

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

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

AB = []
for a in A:
    for b in B:
        AB.append(a + b)
AB.sort(reverse=True)

ABC = []
for ab in AB[:K]:
    for c in C[:K]:
        ABC.append(ab + c)
ABC.sort(reverse=True)

for abc in ABC[:K]:
    print(abc)

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

AB = [a + b for a in A for b in B]
AB.sort(reverse=True)
ABC = [ab + c for ab in AB[:K] for c in C[:K]]
ABC.sort(reverse=True)
[print(abc) for abc in ABC[:K]]
### BUGGY CODE ###

from collections import defaultdict

n, m = map(int, input().split())
prefectures = [list(map(int, input().split())) for _ in range(m)]
ID = defaultdict(list)

for prefecture in prefectures:
    p, y = prefecture
    ID[p].append(y)

for k, v in ID.items():
    v.sort()

for prefecture in prefectures:
    p, y = prefecture
    order = ID[p].index(y) + 1
    print('{:006}{:006}'.format(p, order))

### FIXED CODE ###

n, m = map(int, input().split())
prefectures = [[] for _ in range(10 ** 5)]

for i in range(m):
    p, y = map(int, input().split())
    prefectures[p - 1].append([y, i])

ans = [''] * m
for p in range(10 ** 5):
    prefecture = prefectures[p]
    prefecture.sort(key=lambda x: x[0])
    for i in range(len(prefecture)):
        ans[prefecture[i][1]] = '{:006}{:006}'.format(p + 1, i + 1)

for i in range(m):
    print(ans[i])
### BUGGY CODE ###

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    count = Counter(A)
    for i in range(1, 4):
        if not i in count: count[i] = 0
    x, y, z = count[1], count[2], count[3]
    
    memo = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    
    def dp(a, b, c):
        
        if a == b == c == 0:
            return 0
        
        if a < 0 or b < 0 or c < 0:
            return 0
        
        if a > N or b > N or c > N:
            return 0
        
        if memo[a][b][c] != -1:
            return memo[a][b][c]
        
        res = N
        res += a*dp(a-1, b, c)
        res += b*dp(a+1, b-1, c)
        res += c*dp(a, b+1, c-1)
        res /= a+b+c
        
        memo[a][b][c] = res
        return res
    
    ans = dp(x, y, z)
    
    print(ans)
        
        
    
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

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


N = int(input())
memo = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]

def dp(a, b, c):
    if a == b == c == 0: return 0
    if memo[a][b][c] != -1:
        return memo[a][b][c]
    
    res = N
    if a > 0: res += a*dp(a-1, b, c)
    if b > 0: res += b*dp(a+1, b-1, c)
    if c > 0: res += c*dp(a, b+1, c-1)
    res /= a+b+c
    
    memo[a][b][c] = res
    return res

def main():
    A = list(map(int, input().split()))
    
    count = Counter(A)
    for i in range(1, 4):
        if not i in count: count[i] = 0
    x, y, z = count[1], count[2], count[3]

    
    ans = dp(x, y, z)
    
    print(ans)
        

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

N = int(input())
S = input()
ans = N
for i in range(N + 1):
    ans = min(ans, S[:i].count('#') + S[i:].count('.'))
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ws = S.count('.')
bs = 0
ans = ws + bs
for i in range(N):
    if S[i] == '#':
        bs += 1
    else:
        ws -= 1
    ans = min(ans, ws + bs)
print(ans)
### BUGGY CODE ###

comb = [[0 for i in range(2001)] for k in range(2001)] #comb[i][j] = iCj
mod = int(1e9+7)
for i in range(1,2001):
    comb[i][0] = 1
    comb[i][1] = i
for i in range(2,2001):
    for j in range(2,2001):
        comb[i][j] = comb[i-1][j] + comb[i-1][j-1]
        comb[i][j] %= mod

n,k = map(int,input().split())
for i in range(1,k+1):
    print(comb[n-k+1][i]*comb[k-1][i-1]%mod)

### FIXED CODE ###

mod = int(1e9+7)
stair = [1]
for i in range(1,2001):
    stair.append(stair[i-1]*i)
def comb(stair,n,r):
    return (stair[n]//(stair[n-r]*stair[r]))%mod

n,k = map(int,input().split())
for i in range(1,k+1):
    ans = comb(stair,n-k+1,i) * comb(stair,k-1,i-1)
    print(ans%mod)
### BUGGY CODE ###

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

def z_algo(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    l = len(S)
    A[0] = l

    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while min(l-i, j-A[k]) > k:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

ans = 0
for i in range(N):
    s = S[i:]
    tmp = z_algo(s)
    
    for i in range(1, len(tmp)):
        if tmp[i] > i:
            tmp[i] = 0
    if len(tmp) >= 2:
        ans = max(ans, max(tmp[1:]))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
 
max_len = 0
j = 0
 
for i in range(n):
    while j < n and s[i:j] in s[j:]:
        j += 1
    max_len = max(max_len,j-i-1)
 
print(max_len)
### BUGGY CODE ###

def b_search(a,tgt):
    left = 0
    right = len(a) - 1

    while abs(right - left):
        mid = (left + right) // 2
        if a[mid] > tgt:
            right = mid
        else:
            left = mid
    return a[right]

def main():
    s = input()
    t = input()
    s_set = set(list(s))
    s_dict = {}
    s_len = len(s)
    t_list = list(t)
    t_set = set(t_list)
    c = 0
    ans = []
    ans_append = ans.append
    for i in s_set:
        s_dict[i] = []
    for i in range(s_len):
        s_dict[s[i]].append(i)
    if len(t_set) == len(t_set & s_set):
        for i in t_list:
            idxs = s_dict[i]
            if idxs[-1] <= c:
                c = idxs[0]
                ans_append(c)
            else:
                c = b_search(idxs,c)
                ans_append(c)
        count = 0
        for i in range(len(ans)-1):
            if ans[i] >= ans[i+1]:
                count += 1
        print(s_len*count + ans[-1] + 1)
    else:
        print(-1)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect

def main():
    s = input()
    t = input()
    s_set = set(list(s))
    s_dict = {}
    s_len = len(s)
    t_list = list(t)
    t_set = set(t_list)
    c = -1
    ans = []
    ans_append = ans.append
    for i in s_set:
        s_dict[i] = []
    for i in range(s_len):
        s_dict[s[i]].append(i)
    if len(t_set) == len(t_set & s_set):
        for i in t_list:
            idxs = s_dict[i]
            if idxs[-1] <= c:
                c = idxs[0]
                ans_append(c)
            else:
                c = idxs[bisect.bisect(idxs,c)]
                ans_append(c)
        count = 0
        for i in range(len(ans)-1):
            if ans[i] >= ans[i+1]:
                count += 1
        print(s_len*count + ans[-1] + 1)
    else:
        print(-1)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def dfs(node,visited,friends,connected_compnts):
    cmpnt = set()
    stack = [node]
    while stack:
        curr = stack.pop()
        if curr not in visited:
            visited.add(curr)
            cmpnt.add(curr)
            for kid in friends[curr]:
                stack.append(kid)

    connected_compnts.append(cmpnt)

def solve(cmpnt,friends,blocks,ans):
    arr = list(cmpnt)
    for node in arr:
        cmpnt.remove(node)
        add = []
        for kid in friends[node]:
            if kid in cmpnt:
                add.append(kid)
                cmpnt.remove(kid)

        blocked = set()
        for block in blocks[node]:
            blocked.add(block)
            
        ans[node] = len(cmpnt.difference(blocked))
        cmpnt.add(node)
        for kid in add:
            cmpnt.add(kid)

def main():
    n,m,k = map(int,input().split())
    friends = {}
    blocks = {}

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

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

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

    for i in range(k):
        a,b = map(int,input().split())
        blocks[a].append(b)
        blocks[b].append(a)

    connected_compnts = []

    visited = set()
    for i in range(1,n+1):
        if i not in visited:
            dfs(i,visited,friends,connected_compnts)

    ans = [0]*(n+1)
    for cmpnt in connected_compnts:
        solve(cmpnt,friends,blocks,ans)

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

main()


### FIXED CODE ###

def dfs(node,visited,friends,connected_compnts):
    cmpnt = set()
    stack = [node]
    while stack:
        curr = stack.pop()
        if curr not in visited:
            visited.add(curr)
            cmpnt.add(curr)
            for kid in friends[curr]:
                stack.append(kid)

    connected_compnts.append(cmpnt)

def solve(cmpnt,friends,blocks,ans):
    arr = list(cmpnt)
    for node in arr:
        cmpnt.remove(node)
        add = []
        for kid in friends[node]:
            if kid in cmpnt:
                add.append(kid)
                cmpnt.remove(kid)

        blocked = set()
        for block in blocks[node]:
            blocked.add(block)
            
        ans[node] = len(cmpnt)-len(cmpnt&blocked)
        cmpnt.add(node)
        for kid in add:
            cmpnt.add(kid)

def main():
    n,m,k = map(int,input().split())
    friends = {}
    blocks = {}

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

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

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

    for i in range(k):
        a,b = map(int,input().split())
        blocks[a].append(b)
        blocks[b].append(a)

    connected_compnts = []

    visited = set()
    for i in range(1,n+1):
        if i not in visited:
            dfs(i,visited,friends,connected_compnts)

    ans = [0]*(n+1)
    for cmpnt in connected_compnts:
        solve(cmpnt,friends,blocks,ans)

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

main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
n = int(input())
# スペース区切りの整数の入力
ar = []
for i in range(n):
  ar.append("".join(sorted(input())))

#for t in ar:
#  print(t)
#for i in range(n):
#  for j in range(i+1, n):
#    if ar[i] == ar[j]:
#      ar[j] = ar[i]

count = 0
#for i in range(n):
#  for j in range(i+1, n):
#    if ar[i] is ar[j]:
#      count = count + 1

for i in range(n):
  count = count + ar[i+1:].count(ar[i])

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
N = int(input())

# スペース区切りの整数の入力
ar = []
for i in range(N):
  l = list(input())
  l.sort()
  ar.append("".join(l).__hash__())

# 数を数える
list = {}
for i in ar:
  if i in list:
    list[i] = list[i] + 1
  else:
    list[i] = 1
  
count = 0
for i in list.values():
  n = i - 1
  count = count + int(((n * (n + 1)) / 2))

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

import math
S = input()
Q = int(input())

lr = 'left'

def reverse_list(lr):
    if lr == 'right':
        return 'left'
    else:
    	return 'right'

def moji_tuika(S, f, c, lr):
    if f == 1 and lr == 'left':
        return c + S
    elif f == 1 and lr == 'right':
        return S + c
    elif f == 2 and lr == 'left':
        return S + c
    else:
        return c + S
q = []
for i in range(Q):
    temp = input().split()
    if len(temp) == 1:
        q.append(1)
    else:
        q.append(temp)

for i in q:
    if type(i) == int:
        lr = reverse_list(lr)
    elif int(i[0]) == 2:
        S = moji_tuika(S,int(i[1]),i[2],lr)

if lr == 'right':
    S = list(S)
    S.reverse()
    S = ''.join(S)


print(S)


### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

lr = 'left'

def reverse_list(lr):
    if lr == 'right':
        return 'left'
    else:
        return 'right'

def moji_tuika(S, f, c, lr):
    if f == 1 and lr == 'left':
        S.appendleft(c)
    elif f == 1 and lr == 'right':
        S.append(c)
    elif f == 2 and lr == 'left':
        S.append(c)
    else:
        S.appendleft(c)
    return S

q = []
for i in range(Q):
    temp = input().split()
    if len(temp) == 1:
        q.append(1)
    else:
        q.append(temp)

S = deque(list(S))
for i in q:

    if type(i) == int:
        lr = reverse_list(lr)
    elif int(i[0]) == 2:
        S = moji_tuika(S,int(i[1]),i[2],lr)
if lr == 'right':
    S.reverse()

S = ''.join(S)
print(S)
### BUGGY CODE ###

import sys
import collections


def main():
    # N,M は10^5
    N, M = [int(ele) for ele in input().split()]
    tmp = str(1)*N
    ans = int('0b' + tmp, 2)

    for i in range(M):
        l, r = [int(ele) for ele in sys.stdin.readline().split()]

        secure = int('1' * (r-l+1) + '0' * (N-r), 2)
        ans = ans & secure

    print(bin(ans).count("1"))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import collections


def tle_solver():
    # N,M <=10^5
    N, M = [int(ele) for ele in input().split()]
    ans = int('0b' + str(1)*N, 2)

    for i in range(M):
        l, r = [int(ele) for ele in sys.stdin.readline().split()]
        secure = int('1' * (r-l+1) + '0' * (N-r), 2)
        ans = ans & secure

    print(bin(ans).count("1"))


def ac_solver():
    # N,M <=10^5
    N, M = [int(ele) for ele in input().split()]
    ll = 1
    rr = N
    ans = "Error"

    for i in range(M):
        l, r = [int(ele) for ele in sys.stdin.readline().split()]
        ll = max(ll, l)
        rr = min(rr, r)

    ans = max(0, rr - ll+1)
    print(ans)


if __name__ == "__main__":
    # tle_solver()
    ac_solver()
### BUGGY CODE ###



a,b,c,x,y = map(int,input().split())
p_lists = []
#print(a,b,c,x,y)

if x > y:
  d = x
else:
  d = y

#print(d)

for i in range(x + 1):
    for j in range(y + 1):
        for k in range(2 * d + 1):
            if (i + k / 2 >= x and j + k / 2 >= y):
                price = a * i + b * j + c * k
                p_lists.append(price)      



#print(p_lists)
print(min(p_lists))


### FIXED CODE ###




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

price = a * x + b * y


for i in range(max(x,y) + 1):
    ab = 2 * i
    cand = ab * c + a * max(0, x - i) + b * max(0, y-i)

    price = min(price, cand)

print(price)
### BUGGY CODE ###

n = int(input())
list_XYH = []
m = pow(10, 10)
for _ in range(n):
    x, y, h = map(int, input().split())
    m = min(m, h)
    list_XYH.append([x, y, h])

for X in range(0, 101):
    for Y in range(0, 101):
        for H in range(m, m + 201):
            cnt = 0
            for x, y, h in list_XYH:
                if max(H - abs(x - X) - abs(y - Y), 0) == h:
                    cnt += 1

            if cnt == n:
                print(X, Y, H)
                exit()

### FIXED CODE ###

n = int(input())
list_XYH1, list_XYH = [ list(map(int,input().split(" "))) for _ in range(n)], []
for x, y, h in list_XYH1:
    if h != 0:
        list_XYH.append([x, y, h])

for i in range(0, 101):
    for j in range(0, 101):
        cnt = 0
        x, y, h = list_XYH[0]
        H = h + abs(i - x) + abs(j - y)
        for x, y, h in list_XYH:
            if h + abs(i - x) + abs(j - y) == H:
                cnt += 1

        if cnt == len(list_XYH) and cnt != 0 and cnt != 1:
            print(i, j, H)
            exit()

list_XYH2 = []
m = pow(10, 10)
for x, y, h in list_XYH1:
    m = min(m, h)
    list_XYH2.append([x, y, h])

for X in range(0, 101):
    for Y in range(0, 101):
        for H in range(m, m + 201):
            cnt = 0
            for x, y, h in list_XYH2:
                if max(H - abs(x - X) - abs(y - Y), 0) == h:
                    cnt += 1

            if cnt == n:
                print(X, Y, H)
                exit()
### BUGGY CODE ###

import sys
input=sys.stdin.readline

from math import factorial
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

N = int(input())
A = [0] + list(map(int, input().split()))

B = {}
for i in range(len(A)):
    x = sum(A[0:i+1])
    if x not in B:
        B[x] = 1
    else:
        B[x] += 1

ans = 0
for i in B.values():
    if i >= 2:
        ans += combinations_count(i,2)

print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline

from math import factorial
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

N = int(input())
A = [0] + list(map(int, input().split()))

B = {}
x = 0
for i in A:
    x += i
    if x not in B:
        B[x] = 1
    else:
        B[x] += 1

ans = 0
for i in B.values():
    if i >= 2:
        ans += combinations_count(i,2)

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

S = input()
ans = 0
prev = None
while prev != ans:
    prev = ans
    ans += S.count("BW")
    S = S.replace("BW", "WB")
print(ans)


### FIXED CODE ###

S = list(input())
black = 0
ans = 0
for c in S:
    if c == "B":
        black += 1
    else:
        ans += black
print(ans)