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


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()


def kiku(a):
    print("?",' '.join(map(str,list(range(a,a+N)))))


kiku(1)

T = input()
if T == '-1':
    sys.exit(-1)

baseT = T

L = 1
R = N+1
bmid = INF
while True:
    mid = (L + R)//2
    kiku(mid)
    T = input()
    if T == "-1":
        while True:
            pass
    if T == baseT:
        L = mid
    else:
        R = mid
    if abs(bmid-mid) == 1 and bT != T:
        break
    else:
        bmid = mid
        bT = T

X = max(bmid,mid)

def kikuX(i,X):
    print("?",' '.join(map(str,list(range(X,X+N-1)))),str(i))

ans = [0]*(2*N)

Reds = []
Blues = []

for i in range(1,X):
    kikuX(i,X)
    T = input()[0]
    if T == "R":
        Reds.append(i)
    else:
        Blues.append(i)
    ans[i-1] = T

for i in range(X+N-1,N*2+1):
    kikuX(i,X)
    T = input()[0]
    if T == "R":
        Reds.append(i)
    else:
        Blues.append(i)
    ans[i-1] = T




for i in range(X,X+N-1):
    k = Reds[:N//2] + Blues[:N//2] + [i]
    print("?", ' '.join(map(str,k)))
    ans[i-1] = input()[0]

print('!', ''.join(map(str,ans)))


### FIXED CODE ###


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()


def kiku(a):
    print("?",' '.join(map(str,list(range(a,a+N)))))


kiku(1)

T = input()
if T == '-1':
    sys.exit(-1)

baseT = T

setL = {1}
setR = {N+1}
bmid = INF
bbmid = INF
while True:
    L = max(setL)
    R = min(setR)

    if abs(R-L) == 1:
        break

    mid = (L + R)//2
    kiku(mid)
    T = input()
    if T == baseT:
        setL.add(mid)
    else:
        setR.add(mid)

X = R

def kikuX(i,X):
    print("?",' '.join(map(str,list(range(X,X+N-1)))),str(i))

ans = [0]*(2*N)

Reds = []
Blues = []

for i in range(1,X):
    kikuX(i,X)
    T = input()[0]
    if T == "R":
        Reds.append(i)
    else:
        Blues.append(i)
    ans[i-1] = T

for i in range(X+N-1,N*2+1):
    kikuX(i,X)
    T = input()[0]
    if T == "R":
        Reds.append(i)
    else:
        Blues.append(i)
    ans[i-1] = T




for i in range(X,X+N-1):
    k = Reds[:N//2] + Blues[:N//2] + [i]
    print("?", ' '.join(map(str,k)))
    ans[i-1] = input()[0]

print('!', ''.join(map(str,ans)))
### BUGGY CODE ###

[XYZK,A,B,C] = [input() for i in range(4)]
[X,Y,Z,K] = [int(i) for i in XYZK.split()]
A = sorted([int(i) for i in A.split()],reverse=True)
B = sorted([int(i) for i in B.split()],reverse=True)
C = sorted([int(i) for i in C.split()],reverse=True)
A = A[:K]
B = B[:K]
C = C[:K]
Ans = [0 for i in range(K)]
for a in A:
    for b in B:
        for c in C:
            abc = a+b+c
            if min(Ans) < a + b + c:
                Ans[Ans.index(min(Ans))] = a+b+c
Ans = sorted(Ans,reverse=True)
for i in range(len(Ans)):
    print(Ans[i])

### FIXED CODE ###

[XYZK,A,B,C] = [input() for i in range(4)]
[X,Y,Z,K] = [int(i) for i in XYZK.split()]
A = sorted([int(i) for i in A.split()],reverse=True)[:K]
B = sorted([int(i) for i in B.split()],reverse=True)[:K]
C = sorted([int(i) for i in C.split()],reverse=True)[:K]

ABC = []
for i in range(X):
    if (i + 1) > K:
        break
    for j in range(Y):
        if (i + 1) * (j + 1) > K:
            break
        for l in range(Z):
            if (i + 1) * (j + 1) * (l + 1) > K:
                break
            ABC.append(A[i] + B[j] + C[l])
ABC = sorted(ABC, reverse=True)
print(*ABC[:K])
### BUGGY CODE ###

from operator import mul
from functools import reduce
 
import copy
import sys
input = sys.stdin.readline
 
def combinations(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
 
N = int(input())
 
AList = list(map(int, input().split()))

SortList = copy.copy(AList)
SortList.sort()
 
NumberList = []
CountList = []
tmp = SortList[0]
count = 0
for i in SortList:
    if tmp == i:
        count += 1
    else:
        NumberList.append(tmp)
        CountList.append(count)
        tmp = i
        count = 1
NumberList.append(tmp)
CountList.append(count)
 
CountListCopy = copy.copy(CountList)
 
result = 0
for i in range(0, len(AList)):
    CountListCopy[NumberList.index(AList[i])] -= 1
    for q in CountListCopy:
        if q < 2:
            continue
        else:
            result += combinations(q, 2)
    print(result)
    result = 0
    
    CountListCopy = copy.copy(CountList)

### FIXED CODE ###

from operator import mul
from functools import reduce
import collections
import sys
input = sys.stdin.readline
 
def combinations(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
 
N = int(input())
 
AList = list(map(int, input().split()))

NumberList = set(AList)
CountList = collections.Counter(AList)

result = 0
for i in NumberList:
    if CountList[i] >= 2:
        result += combinations(CountList[i], 2)


for i in AList:
    print(result - (CountList[i] - 1))
### BUGGY CODE ###

import sys

n, m = list(map(int, input().split()))
a_list1 = []
b_list1 = []
a_list2 = []
b_list2 = []

for i in range(m):
    a, b = list(map(int, input().split()))
    if a == 1:
        a_list1.append(a)
        b_list1.append(b)
    elif b == n:
        a_list2.append(a)
        b_list2.append(b)

for i in range(len(a_list1)):
    for j in range(len(a_list2)):
        if b_list1[i] == a_list2[j]:
            print('POSSIBLE')
            sys.exit()

print('IMPOSSIBLE')


### FIXED CODE ###

import sys

n, m = list(map(int, input().split()))
mid_set1 = set([])
mid_set2 = set([])

for i in range(m):
    a, b = list(map(int, input().split()))
    if a == 1:
        mid_set1.add(b)
    elif b == n:
        mid_set2.add(a)

if len(mid_set1&mid_set2) > 0:
    print('POSSIBLE')
    sys.exit()
print('IMPOSSIBLE')
### BUGGY CODE ###

n,m = [int(s) for s in input().split(' ')]

ans = []
anss = None
for i in range(m):
    l,r = [int(s) for s in input().split(' ')]
    temp = set(i for i in range(l,r+1))
    ans.append(temp)
    if i == 0:
        anss = ans[0]
    else:
        anss &= ans[i] 
print(len(anss))

### FIXED CODE ###

n,m = [int(s) for s in input().split(' ')]

ans = []
minn = 10000000
maxx = 0
for i in range(m):
    l,r = [int(s) for s in input().split(' ')]
    maxx = max(maxx,l)
    minn = min(minn,r)
if minn - maxx < 0:
    print(0)
else:
    print(minn - maxx+1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
S = input()
dict_amari = {}
count = 0

henkan = {i: [(10*j+i)%2019 for j in range(2019)] for i in range(1,10)}

def amari_new(dict_amari, s, henkan):
  dict_amari_new = {henkan[k] : v for k,v in dict_amari.items()}
  if s in dict_amari_new.keys():
    dict_amari_new[s] += 1
  else:
    dict_amari_new[s] = 1
  return dict_amari_new

for s in S:
  dict_amari = amari_new(dict_amari, int(s), henkan[int(s)])
  if 0 in dict_amari.keys():
    count += dict_amari[0]

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
S = input()
list_amari = [0 for i in range(2019)]
amari_prev = 0
X = 1

for i in range(len(S)):
  amari = (int(S[-i-1])*X+amari_prev)%2019
  list_amari[amari] += 1
  amari_prev = amari
  X = (10*X)%2019

count = list_amari[0]
for v in list_amari:
  count += v*(v-1)//2

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

N = int(input())
MOD = 10**9+7
a = [int(c) for c in input().split()]
ls = [0]*60
for i in range(N):
  m = a[i]
  for j in range(60):
    if m%2==1:
      ls[j] += 1
    m >>= 1

ans = 0
x = 1
for i in range(60):
  ans += x*(ls[i]*(N-ls[i]))
  ans %= MOD
  x *= 2
  x %= MOD
print(ans)

### FIXED CODE ###

N = int(input())
MOD = 10**9+7
a = [int(c) for c in input().split()]
M = max(a).bit_length()
ls = [0]*M
for i in range(N):
  m = a[i]
  for j in range(M):
    if m%2==1:
      ls[j] += 1
    m >>= 1

ans = 0
x = 1
for i in range(M):
  ans += x*(ls[i]*(N-ls[i]))
  ans %= MOD
  x *= 2
  x %= MOD
print(ans)
### BUGGY CODE ###

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

from itertools import groupby

def gen(s):
  if s[:1] == '0':
  	yield 0
  for ke, g in groupby(s):
    yield len(list(g))
  if s[-1:] == '0':
    yield 0


mc = 0
aaa = list(gen(s))
r = 2 * k + 1
if len(aaa) <= r:
  mc = sum(aaa)
else:
  for i in range(0, len(aaa) - r + 1 , 2):
    mc = max(mc, sum(aaa[i:i+r]))
print(mc)
  
    

### FIXED CODE ###

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

from itertools import groupby, accumulate

def gen(s):
  if s[:1] == '0':
  	yield 0
  for ke, g in groupby(s):
    yield len(list(g))
  if s[-1:] == '0':
    yield 0


mc = 0
acc = list(accumulate(gen(s)))
r = 2 * k + 1
if len(acc) < r:
  mc = n
else:
  for i in range(0, len(acc)-r+1, 2):
    if i == 0:
      mc = max(mc, acc[i+r-1])
    else:
      mc = max(mc, acc[i+r-1] - acc[i-1])
print(mc)
### BUGGY CODE ###

from sys import stdin, setrecursionlimit
from bisect import insort


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()

    for _ in range(m):
        tmp = a[n - 1] // 2
        insort(a, tmp)

    print(sum(a[:n]))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit
from heapq import heapify, heappop, heappush


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a = [-ai for ai in a]
    heapify(a)

    for _ in range(m):
        tmp = -heappop(a)
        heappush(a, -(tmp // 2))

    print(-sum(a))


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

N = int(input())

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

count = 0
while count <= N:
    for i in range(N):
        try:
            if line[i] == i + 1:
                True
            else:
                line.pop(i)
                break
        except:
            break
    count += 1


if len(line) == 0:
    print(-1)
else:
    print(N - len(line))

### FIXED CODE ###

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

checkNum = 1
howMany = 0

for j in range(N):
    if line[j] == checkNum:
        checkNum += 1
    else:
        howMany += 1

# print(line)
# print(checkNum)
# print(howMany)

if checkNum == 1:
    print("-1")
else:
    print(howMany)
### BUGGY CODE ###

import fractions
import functools
n=int(input())
a=list(map(int,input().split()))
A=functools.reduce(fractions.gcd,a)
for i in range(n):
    c=a[i]
    del a[i]
    B=functools.reduce(fractions.gcd,a)
    if A<B:
        A=B
    else:
        A=A
    a.insert(i,c)
print(A)


### FIXED CODE ###

import fractions 
n=int(input())
a=list(map(int,input().split()))
ans=a[0]
sna=a[n-1]
Ans=[ans]*n
Sna=[sna]*n
for j in range(1,n):
  ans=fractions.gcd(ans,a[j])
  Ans[j]=ans
  sna=fractions.gcd(sna,a[n-j-1])
  Sna[j]=sna
m=Sna[n-2]
for k in range(n-2):
  m=max(m,fractions.gcd(Ans[k],Sna[n-3-k]))
m=max(m,Ans[n-2])
print(m)
### BUGGY CODE ###

#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, k = MI()
    p = LI()
    max_seq = 0

    for i in range(n - k + 1):
        if sum(p[i : i + k]) > max_seq:
            max_seq = sum(p[i : i + k])

    print((max_seq + k) / 2)


main()


### FIXED CODE ###

#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    n, k = MI()
    p = LI()
    max_seq = sum(p[:k])

    current = sum(p[:k])

    for i in range(k, n):
        current = current - p[i - k] + p[i]
        max_seq = max(max_seq, current)

    print((max_seq + k) / 2)


main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np
mod = 998244353
n = int(input())
XY = sorted(tuple(map(int, input().split())) for _ in range(n))
X, Y = zip(*XY)
L = {y:i+1 for i, y in enumerate(sorted(Y))}
Y = tuple(L[y] for y in Y)
BIT = [0]*(n+1)
def add(i):
  while i<=n:
    BIT[i] += 1
    i += i&-i
def acc(i):
  res = 0
  while i:
    res += BIT[i]
    i -= i&-i
  return res
A = [0]*n
B = [0]*n
C = [0]*n
D = [0]*n
for i, y in enumerate(Y):
  A[i] = acc(y)
  B[i] = i - A[i]
  add(y)
BIT = [0]*(n+1)
for i in range(n-1, -1, -1):
  y = Y[i]
  C[i] = acc(y)
  D[i] = n-1-i - C[i]
  add(y)
T = [1]*n
for i in range(n-1):
  T[i+1] = T[i]*2%mod
ans = T[n-1] * n % mod
A = np.array(tuple(T[a] for a in A), dtype=np.int64)
B = np.array(tuple(T[b] for b in B), dtype=np.int64)
C = np.array(tuple(T[c] for c in C), dtype=np.int64)
D = np.array(tuple(T[d] for d in D), dtype=np.int64)
temp = (A-1)*B*C*(D-1) + A*(B-1)*(C-1)*D - (A-1)*(B-1)*(C-1)*(D-1)
temp %= mod
cnt = temp.sum()%mod
ans += cnt
ans %= mod
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
mod = 998244353
n = int(input())
XY = sorted(tuple(map(int, input().split())) for _ in range(n))
X, Y = zip(*XY)
L = {y:i+1 for i, y in enumerate(sorted(Y))}
Y = tuple(L[y] for y in Y)
BIT = [0]*(n+1)
def add(i):
  while i<=n:
    BIT[i] += 1
    i += i&-i
def acc(i):
  res = 0
  while i:
    res += BIT[i]
    i -= i&-i
  return res
A = [0]*n
B = [0]*n
C = [0]*n
D = [0]*n
for i, y in enumerate(Y):
  A[i] = acc(y)
  B[i] = i - A[i]
  add(y)
BIT = [0]*(n+1)
for i in range(n-1, -1, -1):
  y = Y[i]
  C[i] = acc(y)
  D[i] = n-1-i - C[i]
  add(y)
ans = pow(2, n-1, mod) * n % mod
for a, b, c, d in zip(A, B, C, D):
  a = pow(2, a, mod)
  b = pow(2, b, mod)
  c = pow(2, c, mod)
  d = pow(2, d, mod)
  temp = (a-1)*b*c*(d-1) + a*(b-1)*(c-1)*d - (a-1)*(b-1)*(c-1)*(d-1)
  ans += temp
  ans %= mod
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
ls = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
  for j in range(n):
    ls[i][j] = min(i,j,n-1-i,n-1-j)
ans = 0
st = set()
for i in a:
  x,y = divmod(i-1,n)
  ans += ls[x][y]
  st.add((x,y))
  q = deque([i-1])
  while q:
    j = q.popleft()
    px,py = divmod(j,n)
    for nx,ny in (px-1,py),(px+1,py),(px,py+1),(px,py-1):
      if 0 <= nx < n and 0 <= ny < n:
        if (px,py) in st:
          if ls[px][py] < ls[nx][ny]:
            ls[nx][ny] = ls[px][py]
            q.append(nx*n+ny)
        elif ls[px][py]+1 < ls[nx][ny]:
          ls[nx][ny] = ls[px][py]+1
          q.append(nx*n+ny)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
n += 2
ls = [0 for i in range(n*n)]
for i in range(n):
  for j in range(n):
    ls[i*n+j] = min(i,j,n-1-i,n-1-j)-1
ans = 0
st = [0]*(n*n)
for i in a:
  x,y = divmod(i-1,n-2)
  i = (x+1)*n+(y+1)
  ans += ls[i]
  st[i]=1
  q = deque([i])
  while q:
    j = q.popleft()
    for k in (j-n,j+n,j+1,j-1):
      if st[j]:
        if ls[j] < ls[k]:
          ls[k] = ls[j]
          q.append(k)
      elif ls[j]+1 < ls[k]:
        ls[k] = ls[j]+1
        q.append(k)
print(ans)
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)
S = str(input())
N = len(S)
M = 13
c = [0]*(N)
for i in range(N):
    c[i] = (10**i)%M
#    c[i] = pow(10,i,M)
#print(c)
c.reverse()
#print(c)
"""
dp = [[0]*M for _ in range(N+1)]
i = int(0)
for j in range(M):
    dp[0][j] = 1
for s in S:
    if s == "?":
        for l in range(10):
            m = l * c[i] % M
            dp[i+1][(M - m) % M] += dp[i][j]
    else:
        m = int(s) * c[i] % M
        dp[i][(M - m) % M] +=dp[i][j]
    i +=1




dp = [[0]*M for _ in range(N)]
c = (10**(N-1))%M
if S[0] == "?":
    for l in range(10):
        dp[0][l*c%M] += 1
else:
    m = int(S[0]) * c%M
    dp[0][m] = 1
S = S[1:]
i = int(1)
for s in S:
    c = (10 ** (N - 1-i)) % M
    if s == "?":
        for j in range(13):
            for l in range(10):
                dp[i][j] += dp[i-1][(j-l*c)%13]
    else:
        st = int(s)
        for j in range(13):
            dp[i][j] = dp[i-1][(j-st*c)%13]
    i +=1

"""
dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1

for i in range(1,N):
    if S[i] == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]
    else:
        for j in range(M):
            m = int(S[i])*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]
    for j in range(M):
        dp[i][j] %=mod

#print(dp)
print(dp[-1][5]%mod)

### FIXED CODE ###

import sys
 
 
def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])
 
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, L=60, MOD=10**9+7):
    modsum = 0
    for j in range(L):
        count_ones = sum([(A[i] >> j) & 1 for i in range(N)])
        count_zeros = N - count_ones
        # MODは一度にとる
        modsum +=  (1<<j) * count_zeros * count_ones
        modsum %= MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))


### FIXED CODE ###

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, L=60, MOD=10**9+7):
    modsum = 0
    for j in range(L):
        count_ones = sum([1 for a in A if (a >> j) & 1])
        # count_ones = sum([(A[i] >> j) & 1 for i in range(N)])
        count_zeros = N - count_ones
        # MODは一度にとる
        modsum +=  (1<<j) * count_zeros * count_ones
        modsum %= MOD
    return modsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))
### BUGGY CODE ###

N = int(input())
I = list(map(int, input().split()))
minX = 10000000000
for i in range(1, len(I)):
  minX = min(minX, abs(sum(I[:-i]) - sum(I[-i:]) ) )
  
print(minX)

### FIXED CODE ###

N = int(input())
I = list(map(int, input().split()))
minX = 10000000000
end = I.pop()
sumI = sum(I)
for i in range(len(I)):
  minX = min(minX, abs(sumI - end ) )
  popped = I.pop()
  sumI -= popped
  end += popped
  
print(minX)
### BUGGY CODE ###

n,m=map(int,input().split())
lst=[]
for i in range(m):
  a,b=map(int,input().split())
  for j in range(a,b+1):
    lst.append(j)
cnt=0
for k in range(1,n+1):
  if lst.count(k)==m:
    cnt+=1
print(cnt)
  

### FIXED CODE ###

n,m=map(int,input().split())
l=[]
r=[]
for i in range(m):
  a,b=map(int,input().split())
  l.append(a)
  r.append(b)
lm=max(l)
rm=min(r)
if rm-lm<0:
  print(0)
else:
  print(rm-lm+1)
### BUGGY CODE ###

n = int(input())
a = [x for x in range(1, n+1)]
print(sum(a) - n)

### FIXED CODE ###

n = int(input())

wa = (n+1)*(n//2)
if n % 2 == 1:
    wa+=(n+1)//2

print(wa-n)
### BUGGY CODE ###

from sys import stdin, setrecursionlimit


def main():
    n, k = map(int, stdin.readline().split())
    p = list(map(int, stdin.readline().split()))

    sp = [0] * n

    for i in range(n):
        sp[i] = sum(range(p[i] + 1)) / p[i]

    max = 0.0

    for i in range(n - k + 1):
        tmp = sum(sp[i: i + k])
        if tmp > max:
            max = tmp

    print(max)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

### FIXED CODE ###

from sys import stdin, setrecursionlimit


def main():
    n, k = map(int, stdin.readline().split())
    p = list(map(int, stdin.readline().split()))

    sp = [0] * 1001

    for i in range(1, 1001):
        sp[i] = sum(range(i + 1)) / i

    summary = [0] * n
    summary[0] = sp[p[0]]
    for i in range(1, n):
        summary[i] = summary[i - 1] + sp[p[i]]

    max = summary[k - 1]
    for i in range(k, n):
        tmp = summary[i] - summary[i - k]
        if tmp > max:
            max = tmp
    print(max)


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

import sys

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# 数と重さで配列を作る
# 値は価値の最大値


def main():
    N, W = map(int, readline().split())
    WV = np.array([[int(x) for x in readline().split()] for _ in range(N)])

    dp = np.zeros([N+1, W+1], np.int64)

    for w, v in WV:
        np.maximum(dp[1:, w:], dp[:-1, :-w] + v, out=dp[1:, w:])

    print(np.max(dp[:, W]))


main()


### FIXED CODE ###

import sys

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N, W = map(int, readline().split())
    WV = np.array([[int(x) for x in readline().split()] for _ in range(N)])

    dp = np.zeros([W+1], np.int64)

    for w, v in WV:
        np.maximum(dp[w:], dp[:-w] + v, out=dp[w:])

    print(np.max(dp))


main()
### BUGGY CODE ###

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

for i in range(1, n+1):
    print(a.count(i))



### FIXED CODE ###

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

ans = [0] * n

for i in lst:
    ans[i-1] += 1

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

import math
a,b=map(int,input().split())
c=math.gcd(a,b)
for x in range(b):
 y=(c-a*x)/b
 if int(y)==y:break
f=lambda x,y:abs(x)+abs(y)
if f(x,y)<f(-b+x,a+y):
 print(x,int(y))
else:
 print(-b+x,int(a+y))


### FIXED CODE ###

r,s=map(int,input().split())
a=d=1;b=c=0
while s:q=r//s;r,s,a,c,b,d=s,r%s,c,a-q*c,d,b-q*d
print(a,b)