Harryxun/stf_run huggingface dataset:
import math
na = lambda: list(map(int, input().split()))
n, X = na()
x = na()
x.append(X)
x.sort()
l = []
for i in range(len(x)-1):
    l.append(x[i+1]-x[i])
ans = l[0]
for i in l[1:]:
    ans = math.gcd(ans, i)
print(ans)

### FIXED CODE ###

from functools import reduce
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
def gcd_list(numbers):
    return reduce(gcd, numbers)
na = lambda: list(map(int, input().split()))
n, X = na()
x = na()
x.append(X)
x.sort()
l = []
for i in range(len(x)-1):
    l.append(x[i+1]-x[i])
print(gcd_list(l))
class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
C = list(map(int, input().split()))

query = []

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

query.sort(key = lambda x: x[1])

lt, rt = 0, 0
L = [None for _ in range(N)]
res = [0 for _ in range(Q)]
bit = BinaryIndexedTree(N)

for l, r, idx in query:
    while rt < r:
        if L[C[rt]] is not None:
            bit.add(L[C[rt]] + 1, -1)
        L[C[rt]] = rt
        bit.add(rt + 1, 1)
        rt += 1
    res[idx] = bit.sum(r) - bit.sum(l)

print('\n'.join(map(str, res)))


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
C = list(map(lambda x: int(x) - 1, input().split()))

query = []

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

query.sort(key = lambda x: x[1])

rt = 0
L = [None for _ in range(N)]
res = [0 for _ in range(Q)]
bit = [0 for _ in range(N + 1)]

for l, r, id in query:
    while rt < r:
        if L[C[rt]] is not None:
            idx = L[C[rt]] + 1
            while idx <= N:
                bit[idx] -= 1
                idx += idx & -idx
        L[C[rt]] = rt
        idx = rt + 1
        while idx <= N:
            bit[idx] += 1
            idx += idx & -idx
        rt += 1
    sr = 0
    sl = 0
    idx = r
    while idx:
        sr += bit[idx]
        idx -= idx & -idx
    idx = l
    while idx:
        sl += bit[idx]
        idx -= idx & -idx
    res[id] = sr - sl

print('\n'.join(map(str, res)))
h,w,a,b = map(int,input().split())
s = [['0']*w for _ in range(h)]

if a == 0 and b == 0:
    print(0)
    exit()
elif a == 0:
    for i in range(b):
        print('1'*w)
    for i in range(h-b):
        print('0'*w)
    exit()
elif b == 0:
    for i in range(h):
        print('1'*a + '0'*(w-a))
    exit()


for i in range(a):
    for j in range(b):
        s[i][j] = '1'

for i in range(h-a):
    for j in range(w-b):
        s[i+a][j+b] = '1'

for i in range(h):
    print(''.join(s[i][:w]))


### FIXED CODE ###

h,w,a,b = map(int,input().split())
s = [['0']*w for _ in range(h)]

for i in range(b):
    for j in range(a):
        s[i][j] = '1'

for i in range(h-b):
    for j in range(w-a):
        s[i+b][j+a] = '1'

for i in range(h):
    print(''.join(s[i]))
# def c():
#     n = int(input())
#     inp = {}
#     for i in range(n):
#         a = input()
#         if inp.get(a) is None:
#             inp[a] = 0
#         inp[a] += 1
#     print(f"AC x {0 if inp.get('AC') is None else inp.get('AC')}")
#     print(f"WA x {0 if inp.get('WA') is None else inp.get('WA')}")
#     print(f"TLE x {0 if inp.get('TLE') is None else inp.get('TLE')}")
#     print(f"RE x {0 if inp.get('RE') is None else inp.get('RE')}")

# c()


h, w, k = [int(x) for x in input.split()]
ans = 0

grid = []

for i in range(h):
    grid.append(input.split())

black = 0

for maskRow in range(0, 1 << h):
    for maskCol in range(0, 1 << w):
        black = 0
        for i in range(h):
            for j in range(w):
                if (maskRow >> i) & 1 == 0 and (maskCol >> j) & 1 == 0 \
                                                    and grid[i][j] == '#':
                    black += 1
    if black == k:
        ans += 1

print(ans)


### FIXED CODE ###

# def c():
#     n = int(input())
#     inp = {}
#     for i in range(n):
#         a = input()
#         if inp.get(a) is None:
#             inp[a] = 0
#         inp[a] += 1
#     print(f"AC x {0 if inp.get('AC') is None else inp.get('AC')}")
#     print(f"WA x {0 if inp.get('WA') is None else inp.get('WA')}")
#     print(f"TLE x {0 if inp.get('TLE') is None else inp.get('TLE')}")
#     print(f"RE x {0 if inp.get('RE') is None else inp.get('RE')}")

# c()


h, w, k = [int(x) for x in input().split()]
ans = 0

grid = []

for i in range(h):
    grid.append(list(input()))

black = 0

for maskRow in range(0, 1 << h):
    for maskCol in range(0, 1 << w):
        black = 0
        for i in range(h):
            for j in range(w):
                if (maskRow >> i) & 1 == 0 and (maskCol >> j) & 1 == 0 \
                                                    and grid[i][j] == '#':
                    black += 1
        if black == k:
            ans += 1

print(ans)
N=int(input())
if N%4==0 or N%7==0:
  print('Yes')
else:
  while 0<N:
    N-=7
    if N%4==0:
      print('Yes')
      break
  else:
    print('No')

### FIXED CODE ###

n,k=map(int,input().split())
if n%k==0:
  print(0)
else:
  print(1)
a = int(input())
if a%2==0:
  print(int((a/2)**2))
else:
  print(int(((a-1)/2)**2)


### FIXED CODE ###

a = int(input())
if a%2==0:
  print(int((a/2)**2))
else:
  print(int(((a-1)/2)*((a+1)/2)))
A,B=input().split()
A=int(A)
B=int(B)
if A*B%2==0 :
  print("Even")
  else :
    print("odd")

### FIXED CODE ###

A,B=input().split()
A=int(A)
B=int(B)
if A*B%2==0 :
  print("Even")
else :
  print("Odd")
n = int(input())
al = [0 for _ in range(n)]
for i in range(n):
    al[i] = int(input())

def check(al,bl,i):
    bl.append(i)
    i = al[i]-1
    if i in bl:
        print(-1)
    elif i == 1:
        print(len(bl))
    else:
        check(al,bl,i)

bl = []
check(al,bl,0)

### FIXED CODE ###

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

i = 0
for j in range(n):
    i = al[i]-1
    if i == 1:
        print(j+1)
        exit()
print(-1)
n =int(input())

if n ==0:
    print(0)
    exit()

l = [(-2)**_ for _ in range(100) if abs((-2)**_) <= 10**10]

if n > 0:
    x = [1]
    for i in range(len(l)):
        if abs(l[i]) < abs(n):
            x.append(l[i+1])

elif n < 0:
    x = []
    for j in range(len(l)):
        if abs(l[j]) < abs(n):
            x.append(l[j])

#print(len(x))

y = []
from itertools import combinations
for __ in range(len(x)):
    y += list(combinations(x, __))

for k in y:
    if sum(k) == n:
        z = list(k)

#print(y)
#print(z)

p = []
for q in range(len(x)):
    if x[q] in z:
        p.append(str(1))
    else:
        p.append(str(0))

p.reverse()
print(''.join(p))


### FIXED CODE ###

def f_10_to_m2(n):
    if n == 0:
        return 0 

    digits = []
    i = 0
    base = 1
    while n != 0:
        if n % (base*2) == 0:
            digits.append(0)
        else:
            digits.append(1)
            n -= base
        i += 1
        base *= -2
    return ''.join(map(str, reversed(digits)))

print(f_10_to_m2(int(input())))
#coding:utf-8
A,B = map(int,input(),split())
if  A >= 13:
    print(B)
elif 6 <= A <= 12:
    print(B / 2)
print(0)

### FIXED CODE ###

#coding:utf-8
A,B = map(int,input().split())
if  A >= 13:
    print(B)
elif 6 <= A and A <= 12:
    print(int(B / 2))
else:
    print(0)
s = input()
t = input()
c = 0
pre = 0
rep = 0
dict = {}
for i, w in enumerate(s):
    if not w in dict.keys():
        dict[w] = []
    dict[w].append(i+1)
for n in t:
    if len(dict[n]) < 1:
        c = -1
        break
    if pre > dict[n][0]:
        rep += 1
    pre = dict[n][0]
    if len(dict[n]) > 1:
        num = dict[n].pop(0)
        dict[n].append(num)
if c == -1:
    print(-1)
else:
    print(len(s) * rep + max(dict[t[-1]]))

### FIXED CODE ###

from bisect import bisect_left
 
ALPHABET = "abcdefghijklmnopqrstuvwxyz"
 
 
def main(s, t):
    positions = {char: [] for char in ALPHABET}
    for i, char in enumerate(s):
        positions[char].append(i)
 
    current = 0
    answer = 0
    for char in t:
        pos_num = len(positions[char])
        if pos_num < 1:
            return -1
        idx = bisect_left(positions[char], current)
        if idx < pos_num:
            current = positions[char][idx] + 1
        else:
            answer += len(s)
            idx = bisect_left(positions[char], 0)
            current = positions[char][idx] + 1
 
    answer += current
    return answer
 
 
s = input()
t = input()
print(main(s, t))
N = int(input())
S = list(map(int,input().split()))
if S.count("Y") == 0:
  print("Three")
else:
  print("Four")

### FIXED CODE ###

N = int(input())
S = list(map(str,input().split()))
if S.count("Y") == 0:
  print("Three")
else:
  print("Four")
from functools import reduce
import numpy as np

mod=10**9+7

def mat(list):
    return reduce(lambda a,b: a*b%mod, list)


N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A = np.array(sorted(A, key=abs, reverse=True))
A_pn = A < 0
print(A_pn)
if N == np.count_nonzero(A_pn):
    if K % 2 == 0:
        print(mat(A[:K]))
    else:
        print(mat(A[-K:]))
elif np.count_nonzero(A_pn[:K]) % 2 == 0:
    print(mat(A[:K]))
else:
    for a in A[K:]:
        if a >= 0:
            last = a
    print(mat(A[:K-1])*last)


### FIXED CODE ###

from functools import reduce
import numpy as np

mod=10**9+7

def mat(list):
    return reduce(lambda a,b: a*b%mod, list)


N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
A = np.array(sorted(A, key=abs, reverse=True))
A_pn = A < 0
if N == np.count_nonzero(A_pn):
    if K % 2 == 0:
        print(mat(A[:K]))
    else:
        print(mat(A[-K:]))
elif np.count_nonzero(A_pn[:K]) % 2 == 0:
    print(mat(A[:K]))
elif N==K:
    print(mat(A))
else:
    negative_all = np.where(A_pn)[0]
    negative_rest = np.count_nonzero(negative_all>=K)
    if negative_rest == 0:
        # 負の数が残っていない
        A[negative_all[-1]] = A[K]
        print(mat(A[:K]))
    elif negative_rest == N-K:
        # 正の数が残っていない
        last_positive = np.where(A_pn[:K]==False)[0][-1]
        A[last_positive] = A[K]
        print(mat(A[:K]))
    elif len(negative_all)-negative_rest==K:
        # 負の数しか選択されていない
        last_negative = negative_all[negative_all<K][-1]
        next_positive = np.where(A_pn==False)[0][0]
        A[last_negative] = A[next_positive]
        print(mat(A[:K]))
    else:
        last_negative = negative_all[negative_all<K][-1]
        next_negative = negative_all[negative_all>=K][0]
        positive_all = np.where(A_pn==False)[0]
        last_positive = positive_all[positive_all<K][-1]
        next_positive = positive_all[positive_all>=K][0]
        if A[last_negative]*A[next_negative] > A[last_positive]*A[next_positive]:
            A[last_positive] = A[next_negative]
        else:
            A[last_negative] = A[next_positive]
        print(mat(A[:K]))
N = list(input())
Sn = 0

for i in N:
    Sn += int(i)

if Sn % N == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())
T = list(str(N))

Sn = 0

for i in T:
    Sn += int(i)

if N % Sn == 0:
    print("Yes")
else:
    print("No")
S = int(input())
s = S % 60
m = S // 60 % 60
h = S // 60 //60
ptint([0][1][2])

### FIXED CODE ###

S = int(input())

s = S % 60
m = S // 60 % 60
h = S // 60 // 60
print(h,':',m,":",s , sep ="")
#print("{a}:{b}:{c}".format(h,m,s))
N = list(input().split())
A = int(N[0])
b1,b2 = N[1].split('.')
B = int(b1+b2)
prd = list(string(A*B))
ans = int(prd[0]+prd[1]+prd[2])
print(ans)


### FIXED CODE ###

N = list(input().split())
A = int(N[0])
b1,b2 = N[1].split('.')
B = int(b1+b2)
prd = list(str(A*B))
ans = 0
if len(prd) < 3:
    ans = 0
else:
    prd.pop()
    prd.pop()
    ans = int(''.join(prd))
print(ans)
X, Y = input().split()
print(X + Y/2)

### FIXED CODE ###

X, Y = map(int, input().split())
print(int(X + Y/2))
H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append(input().split())

T = []
back_n = 0
count = 1
la = []
for i in range(H):
    if "#" in S[i][0]:
        a = []
        c = 0
        if back_n == 0:
            for j in range(W):
                if S[i][0][j] == "#":
                    c += 1
                if S[i][0][j] == "#" and c >= 2:
                    count += 1

                a.append(count)
            T.append(a)
            back_n = 0
            la = a
            count += 1
        else:
            for j in range(W):
                if S[i][0][j] == "#":
                    c += 1
                if S[i][0][j] == "#" and c >= 2:
                    count += 1

                a.append(count)
            for k in range(i - back_n + 1):
                T.append(a)
            back_n = 0
            la = a
            count += 1

    else:
        back_n = i

for k in range(H - len(T) - 1):
    T.append(la)

for i in range(H):
    for j in range(W):
        print(T[i][j], end=" ")
    print(end="\n")


### FIXED CODE ###

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

T = []
back_n = -1
count = 1
la = []
for i in range(H):
    if "#" in S[i][0]:
        a = []
        c = 0
        if back_n == 0:
            for j in range(W):
                if S[i][0][j] == "#":
                    c += 1
                if S[i][0][j] == "#" and c >= 2:
                    count += 1

                a.append(count)
            if back_n == -1:
                T.append(a)
            else:
                for k in range(i - back_n + 1):
                    T.append(a)
            back_n = -1
            la = a
            count += 1
        else:
            for j in range(W):
                if S[i][0][j] == "#":
                    c += 1
                if S[i][0][j] == "#" and c >= 2:
                    count += 1

                a.append(count)

            if back_n == -1:
                T.append(a)
            else:
                for k in range(i - back_n + 1):
                    T.append(a)
            back_n = -1
            la = a
            count += 1

    elif back_n == -1 and not ("#" in S[i][0]):
        back_n = i

for k in range(H - len(T)):
    T.append(la)

for i in range(H):
    for j in range(W):
        print(T[i][j], end=" ")
    print(end="\n")
n,x = map(int,input().split())
ans = 0
cheap = []
for i in range(n):
  now = int(input())
  x -= now
  cheap.append(now)
  ans += 1
ans += x // min(now)
print(ans)

### FIXED CODE ###

n,x = map(int,input().split())
ans = 0
cheap = []
for i in range(n):
  now = int(input())
  x -= now
  cheap.append(now)
  ans += 1
ans += x // min(cheap)
print(ans)
N=int(input())
a=spaceinput()


sa=sorted(a,reverse=True)
x=[]
for i in range(len(sa)-1):
    ssa=sa[i]
    if ssa in x:
        continue
    if sa[i]==sa[i+1]:
        x.append(ssa)
        if len(x)==2:
            break

x.extend([0,0])
print(x[0]*x[1])

### FIXED CODE ###

def spaceinput():
    return list(map(int,input().split(" ")))


N=int(input())
a=spaceinput()


sa=sorted(a,reverse=True)
x=[]
i=0
while True:
    if i>=len(sa)-1:
        break
    ssa=sa[i]
    if sa[i]==sa[i+1]:
        x.append(ssa)
        i+=2
        if len(x)==2:
            break
        continue

    else:
        i+=1


x.extend([0,0])

print(x[0]*x[1])
# coding:utf-8
# C - Grand Garden

N = int(input())
h =  [int(i) for i in input().split()]
h += [0]
ans = 0

for _ in range(1000000):
    mini_ans = 0
    for i in range(N+1):
        if h[i] != 0:
            h[i] -= 1
            add = True
        else:
            if add:
                mini_ans += 1
            add = False
    
    if mini_ans == 0:
        break
    else:
        ans += mini_ans

print(ans)

### FIXED CODE ###

N = int(input())
h = list(map(int,input().split()))
h += [0]
add = False
ans = 0
for n in range(100):
    for i in range(N+1):
        if h[i] != 0:
            h[i] -= 1
            add = True
        else:
            if add:
                ans += 1
            add = False
print(ans)
import math
n,*x=map(int,open(0).read().split())
x.sort()
a=[i-j for i,j in zip(x[1:],x[:-1])]
set(a)
ans=a[0]
b=a[0]
for i in a[1:]:
    ans=min(ans,math.gcd(i,b))
    b=i
print(ans)

### FIXED CODE ###

import fractions
n,*x=map(int,open(0).read().split())
x.sort()
a=[i-j for i,j in zip(x[1:],x[:-1])]
set(a)
a.sort()
b=[i for i in a if i%a[0]]
b.append(a[0])
if len(b)==1:
    print(*b)
else:
    ans=b[0]
    for i in b[1:]:
        ans=fractions.gcd(ans,i)
    print(ans)
N = int(input())
A = list(map(int, input().split()))

def dd_cost(L):
    c = 0
    M = L[:]
    for i in range(len(L)):
        if L[i] < 0:
            L[i] = -1
        elif L[i] > 0:
            L[i] = 1
        else:
            L[i] = 0
    L = np.array(L)
    L = L[1:]-L[:-1]
    for i in range(len(L)):
        if L[i] < 0 or L[i] > 0:
            c += abs(M[i]) * 2
    c += abs(M[-1]) * 2
    print(c)

for i in range(len(A)):
    dd_cost(A[:i]+A[i+1:])


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
A.append(0)
a = 0
cost = 0
for i in A:
    b = i
    cost += abs(a-b)
    a = b
cost += abs(A[-1])

ori = cost
for i in range(1, len(A)-1):
    cost += abs(A[i-1]-A[i+1])
    cost -= abs(A[i-1]-A[i])+abs(A[i+1]-A[i])
    print(cost)
    cost  = ori
N=int(input())

M=[[0]*10 for _ in range(10)]
for i in range(1,N+1):
  S=str(N)
  f=int(S[0])
  b=int(S[-1])
  M[f][s]+=1
  
ans=0
for i in range(10):
  for j in range(10):
    ans+=M[i][j]*M[j][i]
    
print(ans)


### FIXED CODE ###

N=int(input())

M=[[0]*10 for _ in range(10)]
for i in range(1,N+1):
  S=str(i)
  f=int(S[0])
  b=int(S[-1])
  M[f][b]+=1
  
ans=0
for i in range(10):
  for j in range(10):
    ans+=M[i][j]*M[j][i]
    
print(ans)
N,M,X,Y = map(int,input().split())

x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]

c=0
for i in range(X,Y+1):
  c =0
  if (i >=X and i <=Y) :
    c += 1
  if max(x) < i :
    c + =1
  if min(y) < i :
    c += 1
  
  if c == 3:
    print("No War")
    exit()
  else:
    continue
    
    
print("War")


    



### FIXED CODE ###

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

x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]

c=0
for i in range(X+1,Y+1):
  c =0
  if (i >X and i <=Y) :
    c += 1
  if max(x) < i :
    c += 1
  if min(y) >= i :
    c += 1
  
  if c == 3:
   
    print("No War")
    exit()
  else:
    continue
    
    
print("War")
import math
from functools import reduce


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

result = 0
for i in range(n):
    withoutI = a[:i]+a[i+1:]
    tmp = reduce(math.gcd, withoutI)
    if tmp > result:
        result = tmp

print(result)

### FIXED CODE ###

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)


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

l = [0]*(n+2)
r = [0]*(n+2)
m = [0]*(n+2)

for i in range(n+1):
    j = n-i
    if i == 0:  # j = n
        l[i] = 0
        r[j+1] = 0
    else:
        l[i] = gcd(l[i-1], a[i-1])
        r[j] = gcd(r[j+1], a[j])

m = [gcd(l[i], r[i+1]) for i in range(n+1)]

print(max(m))
from fractions import gcd

N = int(input())

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

def lcm(a):
  x = a[0]
  for i in range(1, len(a)):
    x = (x * a[i]) // gcd(x, a[i])
  return x

l = lcm(A)
num=0
for a in A:
  num += int(l/a)
print(int(num % (10**9 +7)))

### FIXED CODE ###

from fractions import gcd

N = int(input())

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

l = A[0]
for a in A:
  l = (l * a) // gcd(l,a)
num=0
for a in A:
  num += l//a
print(num % (10**9 +7))
n = input()
A = [int(x) for x in input().split()]
product = 1
 
for a in A:
    product *= a
    if a = 0:
        break
 
print(product if product <= 10**18 else -1)

### FIXED CODE ###

import sys

n = input()
A = sorted([int(x) for x in input().split()], reverse=True)

if A[-1] == 0:
    print(0)
    sys.exit()

product = 1
for a in A:
    product *= a
    if product > 10**18:
        product = -1
        break

print(product)
a, b, c = map(int, input().split(' '))

if b - a == c - b:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(A: int, B: int):
    if A % 2 != 0 or B % 2 != 0:
        if A > 8 or B > 8:
            print(':(')
            return

    print('Yay!')
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)


if __name__ == '__main__':
    main()
import math

n, k = [int(x) for x in input().split()]

h_n = list(map(int, input().split()))

if n <= k:
    print("0")

s_n = sorted(h_n)

log_sum = math.log(sum(s_n[:n - k]))

print(math.exp(log_sum))

### FIXED CODE ###

import math

n, k = [int(x) for x in input().split()]

h_n = list(map(int, input().split()))

if n <= k:
    print("0")
else:
    s_n = sorted(h_n)

    print(sum(s_n[:n-k]))
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n = II()
    print(int((n / 2 * (n - 1)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n = II()
    print(n  * (n - 1) // 2)

if __name__ == '__main__':
    main()
a,b,c,k = map(int, input().split())

if k <= a:
  print(k)
elif a < k <= a+b:
  print(a):
else:
  print(a - (k - (a+b)))

### FIXED CODE ###

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

if k <= a:
  print(k)
elif a <= k <= a+b:
  print(a)
else:
  print(a - (k - (a+b)))
a=int(input())
b=int(input())
c = int(input())
if a == b == c:
  print(1)
elif a == b or b == c or c == a:
  print(2)
else:
  print(3)

### FIXED CODE ###

a,b,c=map(int,input().split())
if a == b == c:
  print(1)
elif a == b or b == c or c == a:
  print(2)
else:
  print(3)
n, m, k = map(int, input().split())
an = list(map(int, input().split()))
bn = list(map(int, input().split()))

a_sum = [0]
b_sum = [0]
for i in range(1, n+1):
  a_sum.append(a_sum[i-1] + an[i-1])
for j in range(1, m+1):
  b_sum.append(b_sum[j-1] + bn[j-1])

ans = len(bn)
idx = len(bn)
for j in range(m+1):
  if k - b_sum[j] < 0:
    ans = j - 1
    idx = j - 1
    break
for i in range(1, n+1):
  if a_sum[i] + b_sum[idx] > k:
    idx -= 1
  else:
    ans += 1

print(ans)

### FIXED CODE ###

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

a_sum = [0]
b_sum = [0]
for i in range(1, n+1):
  a_sum.append(a_sum[i-1] + an[i-1])
for j in range(1, m+1):
  b_sum.append(b_sum[j-1] + bn[j-1])

idx = len(bn)
ans = 0
for i in range(n+1):
  while a_sum[i] + b_sum[idx] > k:
    idx -= 1
    if idx == -1:
      break
  if idx == -1:
    break
  ans = max(ans, i + idx)

print(ans)