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

import sys
sys.setrecursionlimit(1000000)
def find_root(edges, edges_root, root, searched, before, now):
    searched[now] = True
    edges_root[now] = root
    children = set(edges[now])
    for child in children:
        if child != before and not searched[child]:
            root, edges_root, searched = find_root(edges, edges_root, root, searched, now, child)
    return root, edges_root, searched
    
if __name__ == '__main__':
    N, K, L = map(int, input().split())
    roads = [[] for _ in range(N)]
    rails = [[] for _ in range(N)]
    road_roots = [None]*N
    rail_roots = [None]*N
    answer = [1]*N
        
    for i in range(K):
        p, q = map(int, input().split())
        p -= 1
        q -= 1
        roads[p].append(q)
        roads[q].append(p)
    
    for i in range(L):
        r, s = map(int, input().split())
        r -= 1
        s -= 1
        rails[r].append(s)
        rails[s].append(r)
    
    for i, r in enumerate(road_roots):
        if r is None:
            root, road_roots, group = find_root(roads,road_roots, i, [False]*N, -1, i)


    for i, r in enumerate(rail_roots):
        if r is None:
            root, rail_roots, group = find_root(rails,rail_roots, i, [False]*N, -1, i)

                
    railroads=[[rail, road] for rail, road in zip(road_roots, rail_roots)]

    for n in range(N):
        for d in range(1, N-n):
            if railroads[n] == railroads[n+d]:
                answer[n] += 1 
                answer[n+d] += 1
                
    print(' '.join(list(map(str, answer))))

### FIXED CODE ###

from collections import defaultdict
def build_tree(N, edges):
    root_list = [i for i in range(N)]
    for p, q in edges:
        p -= 1
        q -= 1
        root_p = get_root(root_list, p)
        root_q = get_root(root_list, q)
        root_now = min(root_p, root_q, p)
        root_list[p] = root_now
        root_list[q] = root_now
        root_list[root_p] = root_now
        root_list[root_q] = root_now
    return root_list

def get_root(root_list, city):
    if root_list[city] == city:
        return city
    else: 
        root_list[city] = get_root(root_list, root_list[city])
        return root_list[city]

if __name__ == '__main__':
    N, K, L = map(int, input().split())
    roads = [None]*K
    rails = [None]*L
    for k in range(K):
        roads[k] = list(map(int, input().split()))
    for l in range(L):
        rails[l] = list(map(int, input().split()))
    
    
    '''N = 2*10**5
    L = int(N/2)
    K = int(N/2)
    roads = [None]*K
    rails = [None]*L
    for i in range(L):
        roads[i] = [2*i, 2*i+1]
    for i in range(K):
        rails[i] = [2*i, 2*i+1]'''
    
    road_roots = build_tree(N, roads)
    rail_roots = build_tree(N, rails)
    
    railroads = defaultdict(int)
    RR = []
    for n in range(N):
        rr = (get_root(road_roots, n), get_root(rail_roots, n))
        RR.append(rr)
        railroads[rr] += 1
    answer = [railroads[key] for key in RR]
    print(' '.join(map(str, answer)))
### BUGGY CODE ###

N = int(input())
A_1n = list(map(int, input().split()))
t = 1
for i in A_1n:
  t *= i

if t > 1e18:
  t = -1

print(t)

### FIXED CODE ###

N = int(input())
MX = 10**18
a = list(map(int, input().split()))
if 0 in a:
    print(0)
    exit(0)
ans = 1
for x in a:
    ans *= x
    if ans > MX:
        print(-1)
        exit(0)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)
    colors[(a, b)] = 0
    ed.append([a, b])

col = max(len(v) for v in adj)
cand = set([v for v in range(1, col+1)])

s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break

Q = [[s, -1, set()]]
while Q:
    cur, prev, NG = Q.pop()
    for nex in adj[cur]:
        if nex == prev:
            continue
        colors[(min(cur, nex), max(cur, nex))] = min(cand-NG)
        Q.append([nex, cur, {min(cand-NG)}])
        NG.add(min(cand-NG))
print(col)
for a, b in ed:
    print(colors[(a, b)])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [set() for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    ed.append([a, b])

col = max(len(v) for v in adj)

s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break

Q = [[s, -1, -1]]
while Q:
    cur, prev, NG = Q.pop()
    c = 0
    for nex in adj[cur]:
        if nex == prev:
            continue
        else:
            c += 1
        if c == NG:
            c += 1
        colors[min(cur, nex)*N + max(cur, nex)] = c
        Q.append([nex, cur, c])
print(col)
for a, b in ed:
    print(colors[a*N + b])
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
for i in range(n):
  b = a[:i] + a[i+1:]
  print(max(b))

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
b = sorted(a)
m = b[n-2]
M = b[n-1]
if M == m:
  for i in range(n):
    print(M)
else:
  for i in range(n):
    if a[i] == M:
      print(m)
    else:
      print(M)
### BUGGY CODE ###

def main():
    n = int(input())
    s = list(map(int,input().split()))
    r = []
    for i in range(n,0,-1):
        c = sum(x % i == 0 for x in r)
        c1 = c % 2
        if c1 != s[i-1]:
            r.append(int(i))

    print(len(r))
    if len(r) > 0:
        for i in range(len(r)):
            r[i] = str(r[i])
        print(" ".join(r))
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    s = list(map(int,input().split()))
    r = [0] * n
    for i in range(n,n//2,-1):
        if s[i-1] == 1:
            r[i-1] = 1
    for i in range(n//2,0,-1):
        p = n // i
        c = 0
        for j in range(1,p+1):
            if r[(j * i) - 1] == 1:
                c += 1
        if c % 2 != s[i-1]:
            r[i-1] = 1

    o = sum(r)
    print(o)
    if o > 0:
        u = []
        for i in range(len(r)):
            if r[i] == 1:
                u.append(str(i+1))
        print(" ".join(u))
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def solve():
    K, S = map(int, input().split())
    
    c = 0
    for x in range(K+1):
        for y in range(K+1):
            for z in range(K+1):
                if x+y+z == S:
                    c += 1
    return c

print(solve())


### FIXED CODE ###

def solve():
    K, S = map(int, input().split())
    
    c = 0
    for x in range(K+1):
        for y in range(K+1):
            if 0 <= S-(x+y) <= K:
                z = S-(x+y)
                if x+y+z == S:
                    c += 1
    return c

print(solve())
### BUGGY CODE ###

S = input()[:: -1]
mod = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]

if S[0] == "?":
    for k in range(10):
        dp[1][k % 13] += 1
else:
    dp[1][int(S[0]) % 13] += 1

tmp = 1
for i in range(2, len(S) + 1):
    tmp *= 10 
    tmp %= 13
    for j in range(13):
        if S[i - 1] == "?":
            for k in range(10):
                dp[i][(tmp * k + j) % 13] += dp[i - 1][j] % mod
        else:
            dp[i][(tmp * int(S[i - 1]) + j) % 13] += dp[i - 1][j] % mod

print(dp[len(S)][5] % mod)

### FIXED CODE ###

S = input()[:: -1]
mod = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]

if S[0] == "?":
    for k in range(10):
        dp[1][k % 13] += 1
else:
    dp[1][int(S[0]) % 13] += 1

tmp = 1
for i in range(2, len(S) + 1):
    tmp *= 10
    tmp %= 13
    for j in range(13):
        if dp[i - 1][j] > 0:
            if S[i - 1] == "?":
                for k in range(10):
                    dp[i][(tmp * k + j) % 13] += dp[i - 1][j] % mod
            else:
                dp[i][(tmp * int(S[i - 1]) + j) % 13] += dp[i - 1][j] % mod

print(dp[len(S)][5] % mod)
### BUGGY CODE ###

import sys
from collections import deque

if sys.platform in ['ios','win32','darwin']:
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N, K = MAP()
A = [MAP() for _ in range(N)]

A.sort()
B = deque()
for a in A:
	ai, bi = a
	B.extend([ai]*bi)
# print(B)
print(B[K-1])

### FIXED CODE ###

import sys
from collections import deque

if sys.platform in ['ios','win32','darwin']:
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N, K = MAP()
A = [MAP() for _ in range(N)]

A.sort()
cur = 0
for a in A:
	cur += a[1]
	if cur >= K:
		print(a[0])
		break
### BUGGY CODE ###

s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 0
ident = False
M = max(p[:k])
m = min(p[:k])


for i in range(n - k + 1):
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break
    else:
        if not ident:
            ident = True
            num += 1
        continue

    if i == 0:
        num += 1
        continue
    else:
        if p[i - 1] > min(p[i:i + k - 1]) or p[i + k - 1] < max(p[i:i + k - 1]):
            num += 1      
    

print(num)


### FIXED CODE ###

class MinSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p
        self.start_idx = 0

    def put(self,pos):
        val = self.val_list[pos]

        while len(self.pos_list) > self.start_idx:
            pos1 = self.pos_list[-1]
            val1 = self.val_list[pos1]
            if val1 >= val:
                del self.pos_list[-1]
            else:
                break
        self.pos_list.append(pos)

    def get(self,pos):
        while len(self.pos_list) > self.start_idx:
            pos1 = self.pos_list[self.start_idx]
            if pos1 <= pos:
                self.start_idx += 1
            else:
                break

    def min(self):
        pos1 = self.pos_list[self.start_idx]
        val1 = self.val_list[pos1]
        return val1

class MaxSlideWindow:
    def __init__(self,p):
        self.pos_list = []
        self.val_list = p
        self.start_idx = 0
        
    def put(self,pos):
        val = self.val_list[pos]

        while len(self.pos_list) > self.start_idx:
            pos1 = self.pos_list[-1]
            val1 = self.val_list[pos1]
            if val1 <= val:
                del self.pos_list[-1]
            else:
                break
        self.pos_list.append(pos)

    def get(self,pos):
        while len(self.pos_list) > self.start_idx:
            pos1 = self.pos_list[self.start_idx]
            if pos1 <= pos:
                del self.pos_list[self.start_idx]
            else:
                break

    def max(self):
        pos1 = self.pos_list[self.start_idx]
        val1 = self.val_list[pos1]
        return val1




s = input().split(" ")
n = int(s[0])
k = int(s[1])
sp = input().split(" ")
p = [int(pstr) for pstr in sp]
num = 1
ident = True
rv_pos = -1

minw = MinSlideWindow(p)
maxw = MaxSlideWindow(p)

for i in range(k - 1):
    if p[i] > p[i + 1]:
        rv_pos = i
        ident = False
    
for i in range(k-1):
    minw.put(i)
    maxw.put(i)

for i in range(1,n - k + 1):
    
    maxw.put(i + k - 2)
    minw.put(i + k - 2)
    maxw.get(i-1)
    minw.get(i-1)

    """    
    for j in range(k - 1):
        if p[i + j] > p[i + j +1]:
            break
    else:
        if not ident:
            ident = True
            num += 1
        continue
    """
    if p[i + k - 2] > p[i + k - 1]:
        rv_pos = i + k - 2
        

    
    if rv_pos < i:
        if not ident:
            ident = True
            num += 1
        continue
            

    if p[i - 1] > minw.min() or p[i + k - 1] < maxw.max():
        num += 1

    
print(num)
### BUGGY CODE ###

import math
k=int(input())
ans=0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      tmp=math.gcd(a,b)
      ans+=math.gcd(tmp,c)
print(ans)

### FIXED CODE ###

import math
k=int(input())
ans=0
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      tmp=math.gcd(a,b)
      ans+=math.gcd(tmp,c)
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

min_count = float('inf')
for i in range(n):
    count = 0
    for j in range(n):
        if i == j:
            continue
        elif j < i and s[j] == 'W':
            count += 1
        elif j > i and s[j] == 'E':
            count += 1
    min_count = min(min_count, count)
print(min_count)


### FIXED CODE ###

n = int(input())
s = input()

count = [float('inf')] * n

# 左端
count[0] = 0
for i in range(1, n):
    if s[i] == 'E':
        count[0] += 1

# 尺取
for i in range(1, n):
    count[i] = count[i-1]
    if s[i-1] == 'W':
        count[i] += 1
    if s[i] == 'E':
        count[i] -= 1

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

import re
n,q=map(int,input().split())
s=input()
i=[p.span()[0] for p in re.finditer('(AC){1,1}',s)]
for _ in range(q):
  v=0
  l,r=map(int,input().split())
  for c in i:
    v+= l-1<=c and c+1<=r-1
  print(v)


### FIXED CODE ###

import re
n,q=map(int,input().split())
s=input()
a=[0]*n
b=[0]*n
i=[p.span()[0]for p in re.finditer('(AC){1,1}',s)]
c=0
for m in range(n):
  if c>=len(i):
    if m<n-1:a[m+1]=a[m]
    b[m]=b[m-1]
    continue
  if m==i[c]:
    if m>0:
      if m<n-1:a[m+1]=a[m]+1
      b[m]=b[m-1]+1
    else:
      a[m]=0
      a[m+1]=1
      b[m]+=1
    c+=1
  else:
    a[m+1]=a[m]
    b[m]=b[m-1]
for _ in range(q):
  l,r=map(int,input().split())
  if l>=2:
    print(a[r-1]-b[l-2])
  else:
    print(a[r-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    height_list = list(map(int,input().split()))
    # print(height_list)

    match_count = 0
    for a_i, a_height in enumerate(height_list) :
        for b_i in range(a_i,N) :
            b_height = height_list[b_i]
            height_sum = a_height + b_height
            no_diff = b_i - a_i
            if (height_sum == no_diff) :
                match_count += 1
    
    print(match_count)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

    L = {} # i + Ai
    R = {} # j - Ai
    for i,Ai in enumerate(height_list) :
        l = i + Ai
        if (l not in L.keys()) :
            L[l] = 0
        L[l] += 1

        r = i - Ai
        if (r not in R.keys()) :
            R[r] = 0
        R[r] += 1

    count = 0
    for l_key in L.keys() :
        if (l_key in R.keys()) :
            count += L[l_key] * R[l_key]
    
    print(count)


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

p=input().rstrip().split(' ')
k=int(p[0])
s=int(p[1])
G=0;
for i in range(0,k+1):
    for j in range(0,k+1):
        for k in range(0,k+1):
            if (i+j+k)==s:
                G+=1;
print(G)


### FIXED CODE ###

p=input().rstrip().split(' ')
k=int(p[0])
s=int(p[1])
G=0;
for i in range(0,k+1):
    for j in range(0,k+1):
        b=s-(i+j)
        if b>=0 and b<=k:
            if (i+j+b)==s:
                G+=1;
print(G)
### BUGGY CODE ###

n,m = map(int,input().split(' '))
cost = 0
count = 0

mlist = list()
for i in range(n):
  mlist.append(list(map(int,input().split(' '))))
  mlist.sort(key=lambda x: x[0])

for i in range(n):
  ablist = mlist[i]
  if count+ablist[1] <= m:
    count += ablist[1]
    cost += ablist[0]*ablist[1] 
  else:
    for j in range(ablist[1]):
      count += 1
      if count <= m:
        cost += ablist[0]
      else:
        break_t = True
        break
    if break_t:
      break
print(cost)



### FIXED CODE ###

n,m = map(int,input().split(' '))
cost = 0
count = 0

mlist = list()
for i in range(n):
  mlist.append(list(map(int,input().split(' '))))
mlist.sort(key=lambda x: x[0])

for i in range(n):
  ablist = mlist[i]
  if count+ablist[1] <= m:
    count += ablist[1]
    cost += ablist[0]*ablist[1] 
  else:
    for j in range(ablist[1]):
      count += 1
      if count <= m:
        cost += ablist[0]
      else:
        break_t = True
        break
    if break_t:
      break
print(cost)
### BUGGY CODE ###

from collections import deque
import heapq
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)


# visitedにノードの色を格納する
visited_edge = [[0] * N for _ in range(N)]


# bfsによる色付けを行う
def bfs(now_node):
    queue = deque([[tree[now_node], 0, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1


bfs(0)
ans = []
for a, b in input_list:
    ans.append(visited_edge[a][b])
max_val = 0
for row in visited_edge:
    row.sort()
    tmp_max = row[-1]
    if tmp_max > max_val:
        max_val = tmp_max
print(max_val)
print(*ans, sep="\n")

### FIXED CODE ###

from collections import deque
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)


# visitedにノードの色を格納する
# visited_edge = [[0] * N for _ in range(N)]
dict = {}
'''
# bfsによる色付けを行う
def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val
'''
def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            key = tuple(sorted([now_node, next_node]))
            if not dict.get(key) is None:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            dict[key] = now_color
            # visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val

ans = bfs(0)
print(ans)
for a, b in input_list:
    # print(visited_edge[a][b])
    print(dict[tuple(sorted([a,b]))])
### BUGGY CODE ###

N, M = map(int, input().split())
cand = M // N

while cand > 0:
    if M % cand == 0:
        print(cand)
        exit()
    cand -= 1

### FIXED CODE ###

import math
N, M = map(int, input().split())
 
def enum_divisors(n, reverse=False):
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1 ):
        if n % i == 0:
            divisors.append(i)
            divisors.append(n//i)
    return sorted(divisors, reverse=reverse)
 
 
divisors = enum_divisors(M, reverse=True)
divisors = filter(lambda x: x <= M//N, divisors)
 
for cand in divisors:
    if M % cand == 0:
        print(cand)
        exit()
### BUGGY CODE ###

import sys
from collections import Counter
sys.setrecursionlimit(10**6)
n=int(input())
p=[int(i) for i in input().split()]
a=[]
for i in range(n):
    if p[i]==i+1:
        a.append(i+1)
i=0
b=0
while(i<len(a)):
 if a[i]+2 in a:
   b+=2
   i=a.index(a[i]+2)+1
 else:
   b+=1
   if a[i]+1 in a:
     i+=2
   else:
     i+=1
print(b)

### FIXED CODE ###

n=int(input())
p=[int(i) for i in input().split()]

a=0
b=0
for i in range(n):
    if p[i]==i+1:
        if a==0 or t==i:
           a+=1
        else:
           b+=(a+1)//2
           a=1
        t=i+1
b+=(a+1)//2

print(b)
### BUGGY CODE ###

s=input()
K=int(input())
d=['zzzzz']
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        for k in range(len(d)):
            if s[i:j] not in d and s[i:j]<d[k]:
                d.insert(k,s[i:j])
                if len(d)>5:
                    d.pop()
                break
print(d[K-1])

### FIXED CODE ###

s=input()
K=int(input())
d=['zzzzz']
for i in range(len(s)):
    for j in range(i+1,i+6):
        for k in range(len(d)):
            if s[i:j] not in d and s[i:j]<d[k]:
                d.insert(k,s[i:j])
                if len(d)>5:
                    d.pop()
                break
print(d[K-1])
### BUGGY CODE ###

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


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


def divisor(n):
    i = 1
    d = []
    while i * i <= n:
        if n % i == 0:
            d.append(i)
            if i * i != n:
                d.append(n // i)
        i += 1
    return d


def solve(N, A):
    ans = set()
    for i in range(N, 0, -1):
        if A[i-1] == 1:
            ans.add(i)
            for d in divisor(i):
                A[d-1] ^= 1
    print(len(ans))
    print(*ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


### FIXED CODE ###

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


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


def divisor(n):
    i = 1
    d = []
    while i * i <= n:
        if n % i == 0:
            d.append(i)
            if i * i != n:
                d.append(n // i)
        i += 1
    return d


def solve(N, A):
    ans = []
    for i in range(N, 0, -1):
        if A[i-1] == 1:
            ans += [i]
            for d in divisor(i):
                A[d-1] ^= 1
    print(len(ans))
    print(*ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
### BUGGY CODE ###

n=int(input())
list1=[]
count2=1
ans_sum=[]
#list2=list(0 for _ in range(n))
for i in range(n):
    list1.append(i+1)
for i in range(n):
    count=count2
    ans=[]
    for j in range(n):
        ans.append(list1[j]%count)
        if count==n:
            count=1
        else:
            count+=1
        #print(ans)
    count2+=1
    ans_sum.append(sum(ans))
print(max(ans_sum))


### FIXED CODE ###

n=int(input())
ans=n*(n-1)//2
print(int(ans))