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

N=int(input())
AB=[[0,0]for i in range(N)]
for i in range(N):
    AB[i][0],AB[i][1]=map(int,input().split())
t_delta_AB=[[0,0,i] for i in range(N)]
for i in range(N):
    t_delta_AB[i][1]=AB[i][1]-AB[i][0]
    t_delta_AB[i][0]=AB[i][0]
t_delta_AB.sort(key= lambda x:(x[0],x[1]),reverse=True)
a_delta_AB=[[0,0,i] for i in range(N)]
for i in range(N):
    a_delta_AB[i][1]=AB[i][0]-AB[i][1]
    a_delta_AB[i][0]=AB[i][1]
a_delta_AB.sort(key= lambda x:(x[0],x[1]),reverse=True)
takahashi_score=0
aoki_score=0
buf=[]
for i in range(N):
    if i%2==0:
        n=i
        while 1:
            if not(t_delta_AB[n][2] in buf):
                takahashi_score+=t_delta_AB[n][0]
                buf.append(t_delta_AB[n][2])
                break
            n+=1
    else:
        n=i
        while 1:
            if not(a_delta_AB[n][2] in buf):
                aoki_score+=a_delta_AB[n][0]
                buf.append(a_delta_AB[n][2])
                break
            n+=1
print(takahashi_score-aoki_score)


### FIXED CODE ###

N=int(input())
B=[0 for i in range(N)]
sum_AB=[0 for i in range(N)]
for i in range(N):
    A,B[i]=map(int,input().split())
    sum_AB[i]=A+B[i]
sum_AB.sort(reverse=True)
sum_B=sum(B)
sum_takahashi=-sum_B
i=0
while i<N:
    if i%2==0:
        sum_takahashi+=sum_AB[i]
    i+=1
print(sum_takahashi)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
# print(A)
while len(A) > 1:
    a, b = A[0], A[1]
    c = b % a
    if c == 0:
        A = [a] + A[2:]
    else:
        A = [c,  a] + A[2:]
print(A[0])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
# print(A)
i = 0
while i < len(A) - 1:
    a, b = A[i], A[i + 1]
    A[i] = b % a
    A[i + 1] = a
    if A[i] == 0:
        i += 1
print(A[i])
### BUGGY CODE ###

from collections import Counter

s = input()[::-1]
n = len(s)
counts = [0] * 2019
counts[0] = 1
current = 0
d = 0

for i in range(n):
    current += int(s[i]) * 10**d
    d += 1
    current %= 2019
    counts[current] += 1

ans = 0
for i, count in enumerate(counts):
    if count > 1:
        # print(i)
        ans += count * (count-1) //2
print(ans)


# res = [int(s[a:])%2019 for a in range(n)]
# res.append(0)

# ans = 0
# # count = Counter(res)
# # for i in range(2019):
# #     ans += (count[i] * (count[i] - 1)) // 2
# print(ans)



### FIXED CODE ###

s = input()[::-1]

sum_of_digits = 0

cnts = [0] * 2019

cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

ans = 0
    
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

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

from math import factorial
import collections

def fact(n):
    r = 2
    if n - r < 0:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

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

counts = collections.Counter(BALLS)
for i in range(N):
    print(sum(fact(v if k != BALLS[i] else v - 1) for (k, v) in counts.items()))

### FIXED CODE ###

from math import factorial
import collections

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

MEMO = {}
def fact(n):
    if MEMO.get(n):
        return MEMO[n]
    r = 2
    if n - r < 0:
        MEMO[n] = 0
        return 0
    MEMO[n] = factorial(n) // factorial(r) // factorial(n - r)
    return MEMO[n]

COUNTS = collections.Counter(BALLS)
TOTAL = sum(fact(n) for n in COUNTS.values())

MEMO2 = {}
def solve(n):
    if MEMO2.get(n):
        return MEMO2[n]

    MEMO2[n] = TOTAL - fact(COUNTS[n]) + fact(COUNTS[n] - 1)
    return MEMO2[n]

for i in range(N):
    print(solve(BALLS[i]))
### BUGGY CODE ###

def solve():
    N, *sl = map(lambda x: int(x), open(0).read().split())
    ans = "Yes"
    for i in range(N-1):
        a = sl[i] - 1
        for j in range(i+1, N):
            if sl[j] < a:
                ans = "No"
                break
        else:
            continue
        break
    print(ans)  
if __name__ == '__main__':
    solve()

### FIXED CODE ###

def solve():
    N, *sl = map(lambda x: int(x), open(0).read().split())
    ans = "Yes"
    s_max = sl[0]
    for i in range(1, N):
        a = sl[i]
        if s_max > a + 1:
            ans = "No"
            break
        s_max = max(s_max, a)
    print(ans)  
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

import math
k = int(input())
l = [[i,j,m] for i in range(1,k+1) for j in range(1,k+1) for m in range(1,k+1)]
ans = 0
for i in range(len(l)):
    ans += math.gcd(l[i][2],math.gcd(l[i][0],l[i][1]))
print(ans)

### FIXED CODE ###

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
k = int(input())

ans = 0

for x in range(1,k+1):
    for y in range(1,k+1):
        xy = gcd(x,y)
        for z in range(1,k+1):
            ans += gcd(xy,z)

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

#ABC044C
n,a=map(int,input().split())
x=list(map(int,input().split()))
res=[[0  for i in range(max(1+a*n,1+sum(x)))] for j in range(n+1)]
res[0][0]+=1
for i in range(n):
    for k in range(sum(x),0,-1):
        for j in range(1,n+1):
            if k-x[i]>=0:
                res[j][k]+=res[j-1][k-x[i]]
ans=0
for i in range(1,n+1):
    ans+=res[i][a*i]
print(ans)

### FIXED CODE ###

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

for i in range(N):
    x[i]=int(x[i])
X=max(max(x),A)
for i in range(N):
    x[i]=x[i]-A
dp=[[0 for t in range(2*N*X+1)] for j in range(N+1)]

for j in range(N+1):
    for t in range(2*N*X+1):
        if j==0 and t==N*X:dp[j][t]=1
        elif j>=1:
            if t-x[j-1]<0 or t-x[j-1]>2*N*X:
                dp[j][t]=dp[j-1][t]
            elif t-x[j-1]>=0 and t-x[j-1]<=2*N*X:
                dp[j][t]=dp[j-1][t]+dp[j-1][t-x[j-1]]
print(dp[N][N*X]-1)
#http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-


def factor_osa(A):
    Max = max(A) + 1
    IsPrime = [True] * Max
    MinFactor = [-1] * Max
    Primes = []
    prim = {}
    dica = {}
    mxa = 0
    IsPrime[0], IsPrime[1] = False, False
    MinFactor[0], MinFactor[1] = 0, 1
    for i in range(2, Max):
        if IsPrime[i]:
            MinFactor[i] = i
            Primes.append(i)
            for j in range(i*2, Max, i):
                IsPrime[j] = False
                if MinFactor[j] == -1:
                    MinFactor[j] = i
    ret = []
    for a in A:
        res = []
        while a != 1:
            prime = MinFactor[a]
            exp = 0
            while MinFactor[a] == prime:
                exp += 1
                a //= prime
            res.append((prime, exp))
            if not prime in dica:
                dica[prime] = 1
            else:
                dica[prime] += 1
            mxa = max(mxa, dica[prime])
        ret.append(res)
    return [ret, mxa]

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

aa = factor_osa(a)

from math import gcd        #for python3.8

def Gcd(lt):
    l = len(lt)
    ret = [1]*l
    ret[0] = lt[0]
    for i in range(1,l):
        ret[i] = gcd(ret[i-1], lt[i])
    return ret

if max(a) == 1:
    print('pairwise coprime')
    exit()

if aa[1] == 1:
    print('pairwise coprime')
elif Gcd(a)[-1]==1:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-


def factor_osa(A):
    Max = max(A) + 1
    IsPrime = [True] * Max
    MinFactor = [-1] * Max
    Primes = []
    prim = {}
    dica = {}
    mxa = 0
    IsPrime[0], IsPrime[1] = False, False
    MinFactor[0], MinFactor[1] = 0, 1
    for i in range(2, Max):
        if IsPrime[i]:
            MinFactor[i] = i
            Primes.append(i)
            for j in range(i*2, Max, i):
                IsPrime[j] = False
                if MinFactor[j] == -1:
                    MinFactor[j] = i
    ret = []
    for a in A:
        res = []
        while a != 1:
            prime = MinFactor[a]
            exp = 0
            while MinFactor[a] == prime:
                exp += 1
                a //= prime
            res.append((prime, exp))
            if not prime in dica:
                dica[prime] = 1
            else:
                dica[prime] += 1
            mxa = max(mxa, dica[prime])
        ret.append(res)
    return [ret, mxa]

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

aa = factor_osa(a)

from math import gcd        #for python3.8

def Gcd(lt):
    l = len(lt)
    ret = [1]*l
    ret[0] = lt[0]
    for i in range(1,l):
        ret[i] = gcd(ret[i-1], lt[i])
    return ret

if max(a) == 1:
    print('pairwise coprime')
    exit()

if aa[1] == 1:
    print('pairwise coprime')
elif Gcd(a)[-1]==1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

n,m=map(int,input().split())
ll=[];rl=[];count=0;ans=0
count1=0;count2=0
for i in range(m):
    l,r=map(int,input().split())
    ll.append(l);rl.append(r)
for o in range(n):
    count1+=1
    for i in range(m):

        if ll[i]<=o+1<=rl[i]:
            count2+=1
            
            if count2==m:
                ans+=1
    count2=0
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
ll=[];rl=[]

for i in range(m):
    l,r=map(int,input().split())
    ll.append(l,);rl.append(r)
    
tans=min(rl)-max(ll)+1
if tans>=0:print(tans)
else:print(0)
### BUGGY CODE ###

import copy

s = input().split()[0]

def get_kouho_list(box_list):
    kouho_list = []
    for i, color in enumerate(box_list[:-1]):
        if box_list[i] != box_list[i+1]:
            kouho_list.append((i, i+1))
    return kouho_list

def tansaku(now_box_list, koremade_step):
    kouho_list = get_kouho_list(now_box_list)
    for kouho in kouho_list:
        next_box_list = copy.copy(now_box_list)
        del next_box_list[kouho[0]:kouho[1]+1]
        tansaku(next_box_list, koremade_step + 1)
    global max_step
    if koremade_step > max_step:
        max_step = koremade_step
    return

max_step = 0
tansaku(list(s), 0)
print(max_step * 2)


### FIXED CODE ###

import collections

s = input().split()[0]

counter = collections.Counter(list(s))
c_0 = counter['0']
c_1 = counter['1']
step = min(c_0, c_1)
print(step * 2)
### BUGGY CODE ###

N = int(input())

def pToHW(p):
    p = int(p) - 1
    return divmod(p, N)

P = list(map(pToHW, input().split()))
INF = 10**18

minDist = [[INF] * N for _ in range(N)]
isFilled = [[True] * N for _ in range(N)]


def dfs(h, w):
    st = [(h, w)]
    while st:
        h, w = st.pop()
        dist = minDist[h][w] + (1 if isFilled[h][w] else 0)
        for toH, toW in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if 0 <= toH < N and 0 <= toW < N:
                if minDist[toH][toW] > dist:
                    minDist[toH][toW] = dist
                    st.append((toH, toW))

for i in range(N):
    minDist[i][0] = 0
    minDist[0][i] = 0
    minDist[i][N - 1] = 0
    minDist[N - 1][i] = 0

for i in range(N):
    dfs(i, 0)
    dfs(0, i)
    dfs(i, N - 1)
    dfs(N - 1, i)

ans = 0
for h, w in P:
    ans += minDist[h][w]
    isFilled[h][w] = False
    dfs(h, w)
print(ans)


### FIXED CODE ###

import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('solve', 'i4(i4, i4[:])')
    def solve(N, P):
        minDist = np.ones((N, N), dtype=np.int32)
        isFilled = np.ones((N, N), dtype=np.int32)

        for h in range(N):
            for w in range(N):
                minDist[h][w] = min(h, N - h - 1, w, N - w - 1)

        ans = 0
        for p in P:
            h, w = divmod(p, N)
            ans += minDist[h][w]
            isFilled[h][w] = False

            st = [(h, w)]
            while st:
                h, w = st.pop()
                dist = minDist[h][w] + isFilled[h][w]

                if h + 1 < N and minDist[h + 1][w] > dist:
                    minDist[h + 1][w] = dist
                    st.append((h + 1, w))
                if h - 1 >= 0 and minDist[h - 1][w] > dist:
                    minDist[h - 1][w] = dist
                    st.append((h - 1, w))
                if w + 1 < N and minDist[h][w + 1] > dist:
                    minDist[h][w + 1] = dist
                    st.append((h, w + 1))
                if w - 1 < N and minDist[h][w - 1] > dist:
                    minDist[h][w - 1] = dist
                    st.append((h, w - 1))
        return ans

    cc.compile()
    exit(0)

from my_module import solve

N = int(input())
P = np.asarray(list(map(lambda a: int(a) - 1, input().split())), dtype=np.int32)

print(solve(N, P))
### BUGGY CODE ###

n=int(input())
a=list(input())
left_W=[]
right_E=[]
for i in range(n):
    x=a[:i].count("W")
    left_W.append(x)
    y=a[i+1:].count("E")
    right_E.append(y)
mini=float('inf')
for i in range(n):
    tmp=left_W[i]+right_E[i]
    mini=min(mini,tmp)
print(mini)

### FIXED CODE ###

n=int(input())
a=input()
import collections 
e=a.count("E")
w=0
mini=n
for i in range(n):
    if a[i]=="E":
        e-=1
    if i!=0 and a[i-1]=="W":
        w+=1
    mini=min(mini,e+w)
print(mini)
### BUGGY CODE ###

N = int(input())
lst = []
for i in input().split():
    if i in lst:
        print('NO')
        break
    else:
        lst.append(i)
        
if len(lst) == N:
    print('YES')

### FIXED CODE ###

N = int(input())
U = set()
for i in input().split():
    U.add(i)
print('YES' if len(U) == N else 'NO')
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
AJ = [a - i for i, a in enumerate(A)]

count = 0
for i in range(0, N-1):
    ai = A[i]
    count += list(map(lambda x: x + ai + i, AJ[i+ai:])).count(0)

print(count)

### FIXED CODE ###

N = int(input())
A = tuple(map(int, input().split()))
AI = tuple(i + a for i, a in enumerate(A))
AJ = tuple(i - a for i, a in enumerate(A))

cai = {}
caj = {}
vali = set()
valj = set()
for ai, aj in zip(AI, AJ):
    if not ai in cai:
        cai[ai] = 0
    if not aj in caj:
        caj[aj] = 0

    cai[ai] += 1
    vali.add(ai)

    caj[aj] += 1
    valj.add(aj)

count = 0
for val in vali & valj:
    count += cai[val] * caj[val]

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

N = int(input())
l = []
for i in range(N):
  l.append(list(map(int, input().split())))
  
ans = 0
for i in range(N-1):
  for j in range(i+1, N):
    n = abs(l[i][0]-l[j][0]) + abs(l[i][1]-l[j][1])
    ans = max(ans, n)
print(ans)

### FIXED CODE ###

N = int(input())
L1, L2 = [], []
for i in range(N):
  l = list(map(int, input().split()))
  L1.append(l[0]-l[1])
  L2.append(l[0]+l[1])
  
ans = max(max(L1)-min(L1), max(L2)-min(L2))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
MOD = 998244353
INF = 10 ** 15

def main():
    N,S = map(int,input().split())
    A = list(map(int,input().split()))

    before = [0] * (1 + S)
    before[0] = 1
    ans = 0
    for a in A:
        now = [0] * (1 + S)
        for i in range(S + 1):
            now[i] += before[i]
            if i + a <= S:
                now[i + a] += before[i]
                now[i + a] %= MOD
        now[0] += 1
        ans += now[S]
        ans %= MOD
        before = now
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
MOD = 998244353
INF = 10 ** 15

def main():
    N,S = map(int,input().split())
    A = list(map(int,input().split()))

    before = [0] * (1 + S)
    before[0] = 1
    ans = 0
    for a in A:
        now = [0] * (1 + S)
        for i in range(S + 1):
            now[i] += before[i]
            if i + a <= S:
                now[i + a] += before[i]
                now[i + a] %= MOD
        now[0] += 1
        ans += now[S]
        ans %= MOD
        before = now
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import fractions
from functools import reduce
import itertools

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
  
K = int(input())

ans = 0
for comb in itertools.product(range(1, K+1), repeat=3):
    ans += gcd(*comb)

print(ans)


### FIXED CODE ###

import fractions
from functools import reduce
import itertools
import math

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

if K == 1:
    ans = 1
elif K == 2:
    ans = 9
else:
    ans = 0
    for i in range(1, K+1):
        ans += i
        for j in range(i+1, K+1):
            ans += gcd(i, j) * 6
            for k in range(j+1, K+1):
                ans += gcd(i, j, k) * 6

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

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

ans = 0
for i in range(n):
    ans += a[i] * sum(a[i+1:])

ans = int(ans % (10**9+7))
print(ans)

### FIXED CODE ###

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

a_sum = sum(a)
ans = 0
for i in range(n):
    a_sum -= a[i]
    ans += a[i] * a_sum

ans = int(ans % (10**9+7))
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n, x = map(int, input().split())
slimes = list(map(int, input().split()))

no_magic_cost = sum(slimes)

# 魔法を唱える回数を固定
cost = float('inf')
for k in range(n):
    tmp = 0
    for i in range(n):
        tmp += min([slimes[x % n] for x in range(i-k, i+1)])
    cost = min(cost, tmp+k*x)
print(cost)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n, x = map(int, input().split())
slimes = list(map(int, input().split()))

# 魔法を唱える回数を固定
cost = sum(slimes)
for k in range(n):
    slimes = [slimes[i-1] if slimes[i] > slimes[i-1] else slimes[i]
              for i in range(n)]
    cost = min(cost, sum(slimes)+(k+1)*x)
print(cost)
### BUGGY CODE ###

N, M = map(int, input().split())
root = [set() for i in range(N + 1)]
ans = [0 for i in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    root[a].add(b)
    root[b].add(a)
now = {1}
itta = {1}
while len(now) > 0:
    next = set()
    for i in now:
        next = next | root[i]
    next -= itta
    for i in next:
        num = list(now & root[i])
        num = num[0]
        ans[i] = num
    itta = itta | next
    now = next
print("Yes")
for i in range(2, N + 1):
    print(ans[i])

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
root = [set() for i in range(N + 1)]
ans = [0 for i in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    root[a].add(b)
    root[b].add(a)
task = deque([1])
itta = {1}
while len(task) > 0:
    now = task.popleft()
    additional = root[now] - itta
    for i in additional:
        ans[i] = now
        itta.add(i)
    task.extend(list(additional))
print("Yes")
for i in range(2, N + 1):
    print(ans[i])
### BUGGY CODE ###

S=list(input())
MOD=10**9+7
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
flag=0
ans=0
for i in range(1,len(S)+1):
    if S[-i]=="?":
        for j in range(10):
            a=(j*10**(i-1))%13
            for k in range(13):
                dp[i][(k+a)%13]=dp[i][(k+a)%13]+dp[i-1][k]
    else:
        a=int(S[-i])
        a=(a*10**(i-1))%13
        for k in range(13):
            dp[i][(k+a)%13]=dp[i][(k+a)%13]+dp[i-1][k]
print(dp[len(S)][5]%MOD)

### FIXED CODE ###

S=input()
MOD=10**9+7
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
for i in range(len(S)):
    if S[i]=="?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(10*k+j)%13]+=dp[i][k]%MOD
    else:
        a=int(S[i])
        for k in range(13):
            dp[i+1][(10*k+a)%13]+=dp[i][k]%MOD
print(dp[len(S)][5]%MOD)
### BUGGY CODE ###

import math
import fractions
import collections
import itertools
from collections import deque
d=collections.deque()
S=input()
N=len(S)
cnt=0

amari=[0]*(N+1)
num=0
for i in range(N):
    d.append(int(S[i]))
#print(d)
for i in range(N):
    n=d.pop()
    num=(num+pow(10,i)*n)%2019
    amari[i+1]=num
#print(amari)
#c=collections.Counter(amari)
#values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
amari.sort()
#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
buf=0
#print(amari)
for i in range(N-1):
    if amari[i]==amari[i+1]:
        buf=buf+1
    else:
        cnt=cnt+((buf+1)*buf)//2
        buf=0
    #print(buf)
cnt=cnt+(buf*(buf+1))//2
print(cnt)

### FIXED CODE ###

import math
import fractions
import collections
import itertools
from collections import deque
d=collections.deque()
S=list(input())
N=len(S)
cnt=0

amari=[0]*(N+1)
num=0
for i in range(N):
    d.append(int(S[i]))
#print(d)
for i in range(N):
    n=d.pop()
    num=(num+pow(10,i,2019)*n)%2019
    amari[i+1]=num
#print(amari)
#c=collections.Counter(amari)
#values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
amari.sort()
#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
buf=0
#print(amari)
c=collections.Counter(amari)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
for i in range(len(values)):
    cnt=cnt+(values[i]*(values[i]-1))//2
print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

MOD=998244353
D=[0]*(N+1)
D[1]=1

S=[]
for i in range(K):
    L,R=map(int,input().split())
    S+=[i for i in range(L,R+1)]
    S.sort()

for i in range(2,N+1):
    for j in S:
        if j >i: break
        D[i]+=D[i-j]
    D[i]%=998244353

#print(S)
print(D[N])

### FIXED CODE ###

# -*- coding: utf-8 -*-

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

MOD=998244353
D=[0]*(N+1)
D[1]=1

S=dict()
B=dict()
for i in range(K):
    L,R=map(int,input().split())
    S[i]=(L,R)
    B[i]=0


for i in range(2,N+1):
    for j in range(K):
        L,R=S[j][0],S[j][1]
        if i-L>0: B[j]+=D[i-L]
        if i-R-1>0: B[j]-=D[i-R-1]

        D[i]+=B[j]
        
    D[i]%=998244353

print(D[N])
### BUGGY CODE ###

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

answers = []

answers.append(S.count('.'))
answers.append(S.count('#'))

for i in range(1,N):
  answers.append(S[:i].count('#') + S[i:].count('.'))
  
answer = min(answers)
print(answer)


### FIXED CODE ###

N = int(input())
S = input()
answers = []

from itertools import accumulate

white_cumsum = list(accumulate([1 if s=='.' else 0 for s in S]))
black_cumsum = list(accumulate([1 if s=='#' else 0 for s in S]))

answers.append(white_cumsum[-1])
answers.append(black_cumsum[-1])

for i in range(N):
  answers.append(black_cumsum[i] + white_cumsum[-1] - white_cumsum[i])
    
answer = min(answers)
print(answer)
### BUGGY CODE ###

a, b, k = map(int, input().split())
 
for i in range(k):
  if a > 0:
    a -= 1
  elif b > 0:
    b -= 1
  else:
    break
 
print('{} {}'.format(a, b))

### FIXED CODE ###

a, b, k = map(int, input().split())
 
if a > k:
  print('{} {}'.format(a - k, b))
elif a + b > k:
  print('0 {}'.format(a + b - k))
else:
  print('0 0')
### BUGGY CODE ###

A, B = map(int, input().split(' '))
ans = A
for i in range(A+1, B+1):
  ans = ans^i
print (ans)

### FIXED CODE ###

A, B = map(int, input().split(' '))
def f(x):
  # xor 0 to x
  if x%4 == 0:
    return x
  if x%4 == 1:
    return 1
  if x%4 == 2:
    return 1^x
  if x%4 == 3:
    return 0
  
print (f(A-1) ^ f(B))
### BUGGY CODE ###

X = int(input())

def sum(a):
    x = 0
    for i in range(a+1):
        x += i
    return x

for i in range(1,X+1):
    if sum(i)>= X:
        result = i
        break

print(result)

### FIXED CODE ###

import math
X = int(input())
n = int(math.sqrt(2*X) -2)

def sum(a):
    return a*(a+1)/2

result = 0

for i in range(n,X+1):
    if sum(i)>= X:
        result = i
        break

print(result)
### BUGGY CODE ###

n = int(input())
nlist = [int(input()) for i in range(n)]
xlist = []
c = 0
x = 1
while x != 2 and x not in xlist:
    xlist.append(x)
    x = nlist[x - 1]
    c += 1
if x == 2:
    print(c)
else:
    print(-1)


### FIXED CODE ###

n = int(input())
nlist = [int(input()) for i in range(n)]
c = 0
x = 1
while x != 2 and c < n:
    x = nlist[x - 1]
    c += 1
if x == 2:
    print(c)
else:
    print(-1)