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

N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]


day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		finish[c] = True
		for e in edge[c]:
			parent[e].remove(c)
			if len(parent[e]) == 0:
				new_candidate.append(e)
		edge[c] = []
	candidate = new_candidate
	day += 1
print(day if all(finish) else -1)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]


day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		finish[c] = True
		for e in edge[c]:
			parent[e].remove(c)
			if len(parent[e]) == 0:
				new_candidate.append(e)
		edge[c] = []
	candidate = new_candidate
	day += 1
print(day if all(finish) else -1)
### BUGGY CODE ###

#ABC120C-Unification.py

from sys import stdin

input = stdin.readline

S = input().rstrip()

Nblock = 0

while '0' in S and '1' in S:
    s = S.split('0011')
    Nblock += (len(s)-1)*4
    S = ''.join(s)
    t = S.split('1100')
    Nblock += (len(t)-1)*4
    S = ''.join(t)
    s = S.split('1010')
    Nblock += (len(s)-1)*4
    S = ''.join(s)
    t = S.split('0101')
    Nblock += (len(t)-1)*4
    S = ''.join(t)
    s = S.split('10')
    Nblock += (len(s)-1)*2
    S = ''.join(s)
    t = S.split('01')
    Nblock += (len(t)-1)*2
    S = ''.join(t)

print(Nblock)


### FIXED CODE ###

#ABC120C-Unification.py

from sys import stdin

input = stdin.readline

S = input().rstrip()

Nblock = min(S.count('1'), S.count('0'))

print(Nblock*2)
### BUGGY CODE ###

from collections import defaultdict
N = input()
a_raw = list(map(int, input().split()))
a_plus = [num + 1 for num in a_raw]
a_minus = [num - 1 for num in a_raw]
numbers = set(a_raw) | set(a_minus) | set(a_plus)
num_count = defaultdict(int)
for number in numbers:
    num_count[number] += a_raw.count(number) + a_plus.count(number) + a_minus.count(number)

print(max(num_count.values()))

### FIXED CODE ###

from collections import defaultdict as dd
N = input()
a_raw = list(map(int, input().split()))
num_count = dd(int)
for item in a_raw:
    num_count[item] += 1
    num_count[item-1] += 1
    num_count[item+1] += 1
print(max(num_count.values()))
### BUGGY CODE ###

S = [int(x) if x != '?' else - 1 for x in input()]
le=len(S)

dp = [[0]*13 for i in range(le+1)]
dp[0][0] = 1

i=0
for k in S:
    if k==-1:
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s + j*10) % 13] += dp[i][j]%(10**9+7)

    else:
        k=int(k)
        for j in range(13):
            dp[i + 1][(j *10 + k) % 13] += dp[i][j]%(10**9+7)
        
    i += 1


print(dp[le][5]%(10**9+7))


### FIXED CODE ###

S = [int(x) if x != '?' else - 1 for x in input()]
le=len(S)

dp = [[0]*13 for i in range(le+1)]
dp[0][0] = 1

i=0
for k in S:
    if k==-1:
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s + j*10) % 13] += dp[i][j]%(10**9+7)

    else:
        k=int(k)
        for j in range(13):
            dp[i + 1][(j *10 + k) % 13] += dp[i][j]%(10**9+7)
        
    i += 1


print(dp[le][5]%(10**9+7))
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()

# a, bをfixしてcを探索
# n*n*logn
# b-a < c_i < a+b をにぶたん？
def binary_search(list, item):
    # listからitem以下の最大のindexを取得
    low = 0
    high = len(list) - 1
    if list[high] < item:
        return high+1
    if list[low] >= item:
        return low
    while True:
        mid = (low + high) //2
        guess = list[mid]
        if high - low <= 1:
            return high
        if guess > item:
            high = mid
        else:
            low = mid

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        a = l[i]
        b = l[j]
        c_low = binary_search(l[j+1:], b-a)
        c_high = binary_search(l[j+1:], b+a)
        ans += c_high - c_low
        # print(a, b, c_low, c_high)
print(ans)


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()

# a, bをfixしてcを探索
# n*n*logn
# c_i < a+b をにぶたん
def binary_search(list, item):
    # listからitem未満の最大のindexを取得
    low = 0
    high = len(list) - 1
    if list[high] < item:
        return high+1
    if list[low] >= item:
        return low
    while True:
        mid = (low + high) //2
        guess = list[mid]
        if high - low <= 1:
            return high
        if guess >= item:
            high = mid
        else:
            low = mid

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        a = l[i]
        b = l[j]
        c = binary_search(l, b+a)
        ans += c-(j+1)
print(ans)
### BUGGY CODE ###

from collections import deque
mod = 1000000007

S = input()
L = len(S)
i = L-1
A = [0 for _ in range(L+1)]
B = [0 for _ in range(L+1)]
C = [0 for _ in range(L+1)]
Q = [0 for _ in range(L+1)]
while i >= 0:
    Q[i] = Q[i+1]
    A[i] = A[i+1]
    C[i] = C[i+1]
    B[i] = B[i+1]

    if S[i] == '?':
        Q[i] += 1
    elif S[i] == 'A':
        A[i] += 1
    elif S[i] == 'B':
        B[i] += 1
    elif S[i] == 'C':
        C[i] += 1
    else:
        print("error")
    i -= 1
#i以降にある文字の数

ans = 0
for i in range(L):
    if S[i] in ('B','?'):
        a = A[0] - A[i]
        qleft = Q[0] - Q[i]
        c = C[i+1]
        qright = Q[i+1]
        #print(i)
        #print((a,qleft,c,qright))
        if qleft > 0:
            LEFT = a*3**qleft + qleft*3**(qleft-1)
        else: 
            LEFT = a*3**qleft
        if qright > 0:
            RIGHT = c*3**qright + qright*3**(qright-1)
        else:
            RIGHT = c*3**qright
        LEFT = LEFT%mod
        RIGHT = RIGHT%mod
        number = (LEFT * RIGHT)%mod
        #print(number)
        ans = (ans + number)%mod
print(ans)

### FIXED CODE ###

mod = 1000000007

S = input()
L = len(S)
i = L-1
A = [0 for _ in range(L+1)]
C = [0 for _ in range(L+1)]
Q = [0 for _ in range(L+1)]
while i >= 0:
    Q[i] = Q[i+1]
    A[i] = A[i+1]
    C[i] = C[i+1]

    if S[i] == '?':
        Q[i] = Q[i+1] + 1
    else:
        Q[i] = Q[i+1]

    if S[i] == 'A':
        A[i] = A[i+1] + 1
    else:
        A[i] = A[i+1]
    if S[i] == 'C':
        C[i] = C[i+1] + 1
    else:
        C[i] = C[i+1]
    i -= 1

ans = 0
for i in range(L):
    if S[i] in ('B','?'):
        a = A[0] - A[i]
        qleft = Q[0] - Q[i]
        c = C[i+1]
        qright = Q[i+1]
        if qleft > 0:
            LEFT = a*pow(3,qleft,mod) + qleft*pow(3,qleft-1,mod)
        else: 
            LEFT = a*pow(3,qleft,mod)
        if qright > 0:
            RIGHT = c*pow(3,qright,mod) + qright*pow(3,qright-1,mod)
        else:
            RIGHT = c*pow(3,qright,mod)
        number = (LEFT * RIGHT)%mod
        ans = (ans + number)%mod
print(ans)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

ans = 0

for i in range(n//r+2):
    for j in range((n-r*i)//g+2):
        if n - r*i - g*j >= 0 and (n - r*i - g*j) % b == 0:
            ans += 1

print(ans)


### FIXED CODE ###

r, g, b, n = map(int, input().split())

ans = 0
C = sorted([r, g, b], reverse=True)
r, g, b = C[0], C[1], C[2]

for i in range(n//r+2):
    for j in range((n-r*i)//g+2):
        if n - r*i - g*j >= 0 and (n - r*i - g*j) % b == 0:
            ans += 1

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

def main():
    n = int(input())
    p_list = list(map(int, input().split()))
    count = 1
    for i in range(1, len(p_list)):
      flag = True
      for j in range(i):
          if p_list[i] > p_list[j]:
              flag = False
              break

      if flag:
          count += 1

    print(count)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    p_list = list(map(int, input().split()))
    count = 1
    tmp_min = p_list[0]
    for i in range(1, len(p_list)):
        tmp_min = min(tmp_min, p_list[i])
        if tmp_min == p_list[i]:
            count += 1

    print(count)

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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, A = MAP()
x = LIST()

dp = [[] for _ in range(sum(x)+1)]
dp[0].append(0)

for y in x:
	for i in range(sum(x)-y, -1, -1):
		if dp[i]:
			for z in dp[i]:
				dp[i+y].append(z+1)

ans = 0
for i in range(1, sum(x)//A + 1):
	ans += Counter(dp[i*A])[i]

print(ans)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, A = MAP()
x = LIST()

big = []
small = []
cnt = 0

for y in x:
	if y == A:
		cnt += 1
	elif y < A:
		small.append(A-y)
	else:
		big.append(y-A)

big_possible = [0]*2501
small_possible = [0]*2501
big_possible[0] = 1
small_possible[0] = 1

for a in big:
	for i in range(2500-a, -1, -1):
		if big_possible[i]:
			big_possible[i+a] += big_possible[i]

for b in small:
	for i in range(2500-b, -1, -1):
		if small_possible[i]:
			small_possible[i+b] += small_possible[i]

ans = 1
for i in range(1, 2501):
	ans += small_possible[i]*big_possible[i]


ans *= 2**cnt
print(ans-1)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(list(map(int,input().split())))
ans=n
for i in range(1,n+1):
    for j in range(m):
        if i<a[j][0] or a[j][1]<i:
            ans=ans-1
            break

print(ans)


### FIXED CODE ###

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

s=[]
l= 0
r = n
for i in range(m):
    ln,rn=map(int,input().split())
    if ln>l:
        l=ln
    if rn<r:
        r=rn
if r-l+1>0:
    print(r-l+1)
else:
    print(0)
### BUGGY CODE ###

import sys
from io import StringIO
import unittest


def resolve():
    # s = input()
    n = int(input())
    a = list(map(int, input().split()))
    # l = [list(map(int, input().split())) for _ in range(n)]

    thr = 10 ** 18
    ans = 1

    for a_i in a:
        ans *= a_i

    if ans > thr:
        ans = -1

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2
1000000000 1000000000"""
        output = """1000000000000000000"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
101 9901 999999000001"""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """31
4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0"""
        output = """0"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

import sys
from io import StringIO
import unittest
# import numpy as np

def resolve():
    # s = input()
    n = int(input())
    a = list(map(int, input().split()))
    # l = [list(map(int, input().split())) for _ in range(n)]

    thr = 10 ** 18
    a.sort(reverse=True)
    ans = 1

    if 0 in a:
        ans = 0
    else:
        for a_i in a:
            ans *= a_i

            if ans > thr:
                ans = -1
                break

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2
1000000000 1000000000"""
        output = """1000000000000000000"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
101 9901 999999000001"""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """31
4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0"""
        output = """0"""
        self.assertIO(input, output)


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

limit = 1E18

N = int(input(""))
A = list(map(int, input("").split()))

result = 1
for n in A:
  result = result * n

if result > limit:
  print(-1)
else:
  print(result)

### FIXED CODE ###

N = int(input(""))
A = list(map(int, input("").split()))

limit = 1000000000000000000

result = 1
if 0 not in A:
  for i in A:
    result = result * i
    if result > limit:
      result = -1
      break
else:
  result = 0

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

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

b_init = sum(A)//N - N*(N+1)//(2*N)

while 1:
    #calculate sadness
    sadness = sum([abs(A[i] - (b_init+(i+1))) for i in range(N)])
    sadness_plus1 = sum([abs(A[i] - (b_init+1+(i+1))) for i in range(N)])
    sadness_minus1 = sum([abs(A[i] - (b_init-1+(i+1))) for i in range(N)])
    
    # initial equal ans
    if sadness <= sadness_plus1 and sadness <= sadness_minus1:
        print(sadness)
        break
    
    # right way
    if sadness_plus1 < sadness:
        sad_righter = sadness_plus1
        b = b_init
        while sad_righter <= sadness:
            print(b)
            b+=1
            sadness = sad_righter
            sad_righter = sum([abs(A[i] - (b+(i+1))) for i in range(N)])
    
        print(sadness)
        break
    
    # left way
    if sadness_minus1 < sadness:
        sad_lefter = sadness_minus1
        b = b_init
        while sad_lefter <= sadness:
            print(b)
            b-=1
            sadness = sad_lefter
            sad_lefter = sum([abs(A[i] - (b+(i+1))) for i in range(N)])
    
        print(sadness)
        break

### FIXED CODE ###

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

if N==1:
    print(0)
else:
    B = [A[i]-i for i in range(N)]
    B.sort()
    b_pl = B[N//2]
    b_mn = B[N//2-1]
    
    sadness_pl = sum([abs(B[i]-b_pl) for i in range(N)])
    sadness_mn = sum([abs(B[i]-b_mn) for i in range(N)])
    
    print(min(sadness_pl, sadness_mn))
### BUGGY CODE ###

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime

is_prime = primes(10**5)

Q = int(input())

ans = []
for i in range(Q):
    l, r = map(int, input().split())

    cnt = 0
    for j in range(l, r+1):
        if is_prime[j] and is_prime[(j+1)//2]:
            cnt += 1
    ans.append(cnt)

for a in ans:
    print(a)


### FIXED CODE ###

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime

is_prime = primes(10**5)
like = [False] * 10**5
for i in range(3, 10**5, 2):
    if is_prime[i] and is_prime[(i+1)//2]:
        like[i] = True

cusum = [0] * 10**5
for i in range(3, 10**5, 2):
    cusum[i] = cusum[i-2] + like[i]

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())

    if l == 1:
        print(cusum[r])
    else:
        print(cusum[r] - cusum[l-2])
### BUGGY CODE ###

L, R = map(int, input().split())
mod = 2019
s = 2018
for i in range(L, R):
    for j in range(i+1, R+1):
        t = (i%mod)*(j%mod)%mod
        if s > t:
            s = t
print (s)

### FIXED CODE ###

L, R = map(int, input().split())
mod = 2019
s = 2018
for i in range(L, min(R, L+2018)):
    for j in range(i+1, min(R+1, L+2019)):
        t = (i%mod)*(j%mod)%mod
        if s > t:
            s = t
print (s)
### BUGGY CODE ###

## abc070d: Transit Tree Path

n = int(input())

T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    T[v1] = T[v1] + [[v1,v2,d]] if(T[v1]) else [[v1,v2,d]]
    T[v2] = T[v2] + [[v2,v1,d]] if(T[v2]) else [[v2,v1,d]]

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

depth = [0]*(n+1)
visit = [False]*(n+1)
depth[k] = 0
visit[k] = True
stack = T[k]
while stack:
    p,c,d = stack.pop()
    if visit[c]: continue
    visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])

### FIXED CODE ###

## abc070d: Transit Tree Path

n = int(input())

T = [None]*(n+1)
for _ in range(n-1):
    v1,v2,d = map(int, input().split())
    if(T[v1] is None): T[v1] = [[v1,v2,d]]
    else: T[v1].append([v1,v2,d])
    if(T[v2] is None): T[v2] = [[v2,v1,d]]
    else: T[v2].append([v2,v1,d])

depth = [0]*(n+1)

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

is_visit = [False]*(n+1)
p,c,d = 0,k,0
depth[c] = d
is_visit[c] = True
stack = T[c]
while stack:
    p,c,d = stack.pop()
    if is_visit[c]: continue
    is_visit[c] = True
    depth[c] = depth[p] + d
    for pp,cc,dd in T[c]:
        if not is_visit[cc]: stack.append([pp,cc,dd])

for _ in range(q):
    v1,v2 = map(int, input().split())
    print(depth[v1]+depth[v2])
### BUGGY CODE ###

N = int(input())
HP_list = [int(i) for i in input().split()]
while len(HP_list)>1:
    HP_list.sort()
    HP_max = HP_list.pop(-1)
    attacked_list = [HP_max%i for i in HP_list]
    HP_list.append(min(attacked_list))
    HP_list.sort()
    if HP_list[0] == 0:
        HP_list.pop(0)
print(HP_list[0])

### FIXED CODE ###

import numpy as np
N = int(input())
HPs = np.array([int(i) for i in input().split()])
np.sort(HPs)
while len(HPs) > 1:
    HPs[1:] %= HPs[0]
    HPs[HPs==0] = HPs[0]
    HPs=np.unique(HPs)
print(HPs[0])
### BUGGY CODE ###

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

loop_li = []
a = 1 

while a not in loop_li:
    loop_li.append(a)
    a = a_li[a-1]

length = len(loop_li)
if k<length:
    print(loop_li[k])
else:
    bp = a_li[loop_li[-1]-1] # back point
    bp_idx = loop_li.index(bp)
    t = length - bp_idx
    amari = (k-bp_idx)%t
    print(loop_li[bp_idx+amari])

### FIXED CODE ###

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

loop_li = []
loop_set = set([])
a = 1 

while a not in loop_set:
    loop_li.append(a)
    loop_set.add(a)
    a = a_li[a-1]

length = len(loop_li)
if k<length:
    print(loop_li[k])
else:
    bp = a_li[loop_li[-1]-1] # back point
    bp_idx = loop_li.index(bp)
    t = length - bp_idx
    amari = (k-bp_idx)%t
    print(loop_li[bp_idx+amari])
### BUGGY CODE ###

binary = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 73741817, 147483634, 294967268, 589934536, 179869065, 359738130, 719476260, 438952513, 877905026, 755810045, 511620083, 23240159, 46480318, 92960636, 185921272, 371842544, 743685088, 487370169, 974740338, 949480669, 898961331, 797922655, 595845303, 191690599, 383381198, 766762396, 533524785, 67049563, 134099126, 268198252, 536396504]

n = int(input())
a = [format(i,"b") for i in map(int, input().split())]
mod = 10**9+7
b = [0 for _ in range(61)]

for i in range(n):
    for j in range(len(a[i])):
        b[j] += int(a[i][-j-1])

result = 0
for i in range(61):
    r = b[i]*(n-b[i])%mod
    r = r*binary[i]%mod
    result += r
print(result%mod)

### FIXED CODE ###

import numpy as np
mod = 10**9+7
n = int(input())
a = np.fromstring(input(), dtype = np.int64, sep = ' ')

result = 0
for i in range(60):
    count_one = int((a&1).sum())
    result += count_one*(n-count_one)*(2**i)
    a >>= 1
print(result%mod)
### BUGGY CODE ###

N=int(input())
AS = list(map(int,input().split()))
zero=False
sum = 1
for i in range(len(AS)):
  A=AS[i]
  if A==0:
    zero=True
    break
  sum = sum * A
if zero==True:
  print(0)
else:
  if sum > 10**18:
    print(-1)
  else:
    print(sum)

### FIXED CODE ###

N=int(input())
AS = list(map(int,input().split()))
if 0 in AS:
  print(0)
  exit()
s = 0
sum = 1
l=len(AS)
for i in range(l):
  A=AS[i]
  sum = sum * A
  if sum > 10**18:
    s=2
    break
if sum > 10**18:
  print(-1)
else:
  print(sum)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
c,s=[0]*n,set()
c[1]=abs(h[0]-h[1])
for i in range(2,n):
    for j in range(max(0,i-k),i):
        s.add(c[j]+abs(h[i]-h[j]))
    c[i]=min(s)
    s.clear()
print(c[-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
c=[0]*n
for i in range(1,n):
    c[i]=min([cj+abs(h[i]-hj) for cj,hj in zip(c[max(0,i-k):i],h[max(0,i-k):i])])
print(c[-1])
### BUGGY CODE ###

a=0
S=input()
N=len(S)
for i in range(N-3):
  for j in range(i+3,N):
    if sum(list(map(int,S[i:j+1])))%3==0:
      if int(S[i:j+1])%673==0:
        a=a+1
print(a)

### FIXED CODE ###

ans=0
S=input()
a=len(S)
k=0
c=dict()
mod=2019
s=1
c[0]=1
for i in range(a):
  k+=(s*int(S[a-i-1]))
  k%=mod
  s*=10
  s%=mod
  if k in c:
    c[k]+=1
  else:
    c[k]=1
for i in c:
  ans+=c[i]*(c[i]-1)//2
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    ans = 0

    for i in range(n-1):
        ans += i+1

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())

    # for i in range(n-1):
    #     ans += i+1

    # print(ans)

    print(((n-1) * n) // 2)

if __name__ == '__main__':
    main()