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

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


class Solver(object):
    def __init__(self):
        pass

    def solve(self, n, arr):
        sum = 0
        bitcount = [0]*100
        for num in arr:
            b = reversed(list(bin(num))[2:])
            for i, s in enumerate(b):
                bitcount[i] += int(s)
        for i, b in enumerate(bitcount):
            sum += b * (n-b) * 2**i
        return sum % (10**9 + 7)


def main():
    N = int(input())
    A_l = [int(i) for i in input().split()]
    solver = Solver()
    print(solver.solve(N, A_l))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def solve(n, arr):
    sum = 0
    bitcount = [0]*100
    for num in arr:
        b = reversed(bin(num)[2:])
        for i, s in enumerate(b):
            if i != "0":
                bitcount[i] += int(s)
    for i, b in enumerate(bitcount):
        sum += b * (n-b) * 2**i
    return sum % (10**9 + 7)


def main():
    N = int(input())
    A_l = [int(i) for i in input().split()]
    print(solve(N, A_l))


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

n,q=map(int,input().split())
s=input()
ans=0
for i in range(q):
    l,r=map(int,input().split())
    ans=0
    for i in range(l-1,r-1):
        if s[i:i+2]=="AC":
            ans+=1
    print(ans)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
count=[0]*n
for i in range(1,n):
    count[i]+=count[i-1]
    if s[i-1:i+1]=="AC":
        count[i]+=1
for i in range(q):
    l,r=map(int,input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
 
b=list(set(a))
c=0
for i in b:
    nc=0
    for j in range(len(a)):
        if a[j]==i:
          nc+=1
        else:
          nc+=0    
    c+= nc-i if nc-i>=0 else nc
print(c)

### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))
counter=Counter(a)
b=list(set(a))
c=0
for i in b:
    k =  counter[i]
    c+= k-i if k-i>=0 else k
print(c)
### BUGGY CODE ###

def main():
    def fcalc(cl,c):
        f = 0
        for i in range(len(cl)):
            if cl[i] != c:
                f += d[cl[i]-1][c-1]
        return f
                
    n,c = map(int,input().split())
    d = [list(map(int,input().split())) for _ in range(c)]
    color = [list(map(int,input().split())) for _ in range(n)]
    clist = [[],[],[]]
    for i in range(n):
        for j in range(n):
            clist[(i+j+2)%3].append(color[i][j])
    ans_list = []
    for i in range(1,c+1):
        for j in range(1,c+1):
            for k in range(1,c+1):
                if not (i==j or j == k or k == i):
                    f1 = fcalc(clist[0],i)
                    f2 = fcalc(clist[1],j)
                    f3 = fcalc(clist[2],k)
                    ans_list.append(f1+f2+f3)
    print(min(ans_list))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
def main():
    def fcalc(cl,c):
        f = 0
        for i in cl.keys():
            if i != c:
                f += d[i-1][c-1]*cl[i]
        return f
                
    n,c = map(int,input().split())
    d = [list(map(int,input().split())) for _ in range(c)]
    color = [list(map(int,input().split())) for _ in range(n)]
    clist = [defaultdict(int),defaultdict(int),defaultdict(int)]
    for i in range(n):
        for j in range(n):
            clist[(i+j+2)%3][color[i][j]] += 1
    ans_list = []
    for i in range(1,c+1):
        f1 = fcalc(clist[0],i)
        for j in range(1,c+1):
            if i != j:
                f2 = fcalc(clist[1],j)
                for k in range(1,c+1):
                    if j != k and k != i:
                        f3 = fcalc(clist[2],k)
                        ans_list.append(f1+f2+f3)
    print(min(ans_list))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

K , S = map(int , input().split())
count = 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:
	      count += 1
print(count)


### FIXED CODE ###

K , S = map(int,input().split())
cnt = 0
for x in range(K + 1):
    for y in range(K + 1):
        if x + y > S:
            continue
        z = S - x - y
        if z <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

from itertools import accumulate

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


for _ in range(k):
    tmp = [0] * (n + 2)
    for i in range(n):
        power = arr[i]
        left = max(0, i - power + 1)
        right = min(n + 1, i + power + 2)
        tmp[left] += 1
        tmp[right] -= 1
    arr = list(accumulate(tmp))[1:-1]

print(*arr)

### FIXED CODE ###

from itertools import accumulate
import sys

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

for cnt in range(k):
    tmp = [0] * (n + 2)
    for i in range(n):
        power = arr[i]
        left = max(0, i - power + 1)
        right = min(n + 1, i + power + 2)
        tmp[left] += 1
        tmp[right] -= 1
    arr = list(accumulate(tmp))[1:-1]
    if cnt > 40:
        arr = [n] * n
        print(*arr)
        sys.exit()

print(*arr)
### BUGGY CODE ###

N, M = map(int, input().split())
path = [[float("inf")]*N for i in range(N)]
ans = [[[float("inf")]]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    path[a-1][b-1] = c
    path[b-1][a-1] = c
    ans[a-1][b-1] = [i]
    ans[b-1][a-1] = [i]
for i in range(N):
    path[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if path[i][k]+path[k][j] < path[i][j]:
                path[i][j] = path[i][k]+path[k][j]
                ans[i][j] = ans[i][k]+ans[k][j]
total = []
for i in range(N):
    for j in range(N):
        if ans[i][j] != [float("inf")]:
            total = ans[i][j] + total
print(M-len(set(total)))
        


### FIXED CODE ###

N, M = map(int, input().split())
path = [[float("inf")]*N for i in range(N)]
ans = [[[float("inf")]]*N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    path[a-1][b-1] = c
    path[b-1][a-1] = c
    ans[a-1][b-1] = [i]
    ans[b-1][a-1] = [i]
for i in range(N):
    path[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if path[i][k]+path[k][j] < path[i][j]:
                path[i][j] = path[i][k]+path[k][j]
                ans[i][j] = ans[i][k]+ans[k][j]
total = set()
for i in range(N):
    for j in range(N):
        p = set(ans[i][j])
        total = total|p
print(M-len(set(total))+1)
### BUGGY CODE ###

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N)]
time = 0
ab = sorted(ab, key=lambda x:x[1])
while ab:
  a, b = ab.pop(0)
  time += a
  if time <= b:
    pass
  else:
    print('No')
    exit()
print('Yes')

### FIXED CODE ###

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N)]
time = 0
ab = sorted(ab, key=lambda x:x[1])
for a, b in ab:
  time += a
  if time <= b:
    pass
  else:
    print('No')
    exit()
print('Yes')
### BUGGY CODE ###

n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [0]*(n+1)
memo[0]=1
su = 0
if 1 in l:
  memo[1]=0
else:
  memo[1]=1

for i in range(2,n+1):
  if i in l:
    continue
  else:
    memo[i]=(memo[i-1]+memo[i-2])%q
print(memo[-1]%q)

### FIXED CODE ###

n,m = map(int,input().split())
l = [int(input()) for _ in range(m)]
q = 10**9+7
memo = [-1]*(n+1)
memo[0]=1
su = 0
if 1 in l:
  memo[1]=0
else:
  memo[1]=1
for j in l:
  memo[j]=0
  
for i in range(2,n+1):
  if memo[i]==0:
    continue
  else:
    memo[i]=((memo[i-1]%q)+(memo[i-2]%q))%q
print(memo[-1]%q)
### BUGGY CODE ###

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

B = [0] * (N+1)
B[0] = 1 - A[0]
for i in range(0,N):
    if 2*B[i] < A[i+1]:
        print("-1")
        exit()
    B_max = sum(A[i+2:])
    B[i+1] = min(2*B[i]-A[i+1],B_max)
if B[-1] != 0:
    print("-1")
else:
    print(sum(A)+sum(B))


### FIXED CODE ###

N = int(input())
#葉
A = list(map(int,input().split()))
s = sum(A[1:])
B = [0] * (N+1)
B[0] = 1 - A[0]
for i in range(0,N):
    s -= A[i+1]
    if 2*B[i] < A[i+1]:
        print("-1")
        exit()
    B[i+1] = min(2*B[i]-A[i+1],s)
if B[-1] != 0:
    print("-1")
else:
    print(sum(A)+sum(B))
### BUGGY CODE ###

import heapq
import sys
N = int(input())

HQ = []
g = [[]*N for _ in range(N)]
all = 0
for i in range(N):
  temp = list(map(int,(input().split())))
  g[i] = temp
  all += sum(temp)
#print(g,all)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if g[i][j] > g[i][k] + g[k][j]:
        print("-1")
        sys.exit()
      elif g[i][j] == g[i][k] + g[k][j] and i != j and j != k and k != i:
        #print(i,j,g[i][j])
        all -= g[i][j]
print(all//2)

### FIXED CODE ###

import heapq
import sys
N = int(input())

r = [[1]*N for _ in range(N)]
g = [[]*N for _ in range(N)]
all = 0
for i in range(N):
  temp = list(map(int,(input().split())))
  g[i] = temp
  all += sum(temp)
#print(g,all)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if g[i][j] > g[i][k] + g[k][j]:
        print("-1")
        sys.exit()
      elif g[i][j] == g[i][k] + g[k][j] and i != j and j != k and k != i:
        r[i][j] = 0
ans = 0
for i in range(N):
  for j in range(N):
    ans += g[i][j]*r[i][j]

ans = ans//2
print(ans)
### BUGGY CODE ###

def main():
    n,k = map(int, input().split())
    town = list(map(int, input().split()))
    set_t = set()
    list_t = []
    current = 1
    is_loop = False
    counter = {}
    for i in range(k):
        current = town[current-1]
        set_t.add(current)
        list_t.append(current)
        if len(list(set_t)) != len(list_t):
            loop_start = counter[list_t[-1]]
            is_loop = True
            break
        counter[current] = i
    if not is_loop:
        print(list_t[-1])
    else:
        loop_list = list_t[loop_start:-1]
        am = (k-i) % len(loop_list)
        print(loop_list[am-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n,k = map(int, input().split())
    town = list(map(int, input().split()))
    town = [i-1 for i in town]
    visited = [-1] * n
    current_town = 0
    current_order = 0
    memo = []
    while visited[current_town] == -1:
        visited[current_town] = current_order
        memo.append(current_town)
        current_town = town[current_town]
        current_order += 1
    loop_start = visited[current_town]
    if k < len(memo):
        print(memo[k]+1)
    else:
        loop_length = len(memo) - loop_start
        k =  (k - loop_start) % loop_length
        print(memo[k+loop_start]+1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    n,m=map(int,input().split())
    p = list(map(int,input().split()))
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n
    
        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]
    
        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
    
            if x == y:
                return
    
            if self.parents[x] > self.parents[y]:
                x, y = y, x
    
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        
        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]
    
        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]
        
        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}
    
          
    uf = UnionFind(n)
    for i in range(m):
        x,y = map(int,input().split())
        uf.union(x-1,y-1)
    
    ans=0
    groups = uf.all_group_members().values()
    for cand in groups:
        ans+=len(set(cand) & set(p[i]-1 for i in cand) )
    print(ans)
    
main()

### FIXED CODE ###

n,m=map(int,input().split())
p = [int(i)-1 for i in input().split() ]


tree=[[] for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

from collections import deque

groups=[]
been=[0]*n
for i in range(n):
    if been[i]==0:
        group=[i]
        been[i]=1
        q = deque([(i,togo) for togo in tree[i]]) 
        while q:
            parent,x = q.popleft()
            if been[x]==1:
                continue
            been[x]=1
            group.append(x)
            for y in tree[x]:
                if y == parent:#親ノードを飛ばし
                    continue
                q.append((x,y))#子ノードを追加
        groups.append(group)

ans=0
for group in groups:
    ans+= len( set(group) & set(p[g] for g in group) )

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

from itertools import accumulate
n, k = map(int, input().split())
As = list(map(int, input().split()))

acc = [0]+list(accumulate(As))
mx = 0
sums = []
for i in range(n+1):
    for j in range(i+1,n+1):
        s = acc[j]-acc[i]
        sums.append(s)

# 計算
ans = 0
now = 0
for d in range(40,-1,-1):
    cnt = 0
    for s in sums:
        # 上から見て、bitが立っている数がkこ以上かどうか
        # 1000 -> 1100 -> 1100 -> 1101 みたいな絞り込み
        # 何故か、
        if s & (now+(1<<d)) == now+(1<<d):
            cnt += 1
    # print(d,cnt)
    if cnt >= k:
        now += 1<<d
print(now)

### FIXED CODE ###

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

from itertools import accumulate
acc = [0]+list(accumulate(As))
dp = [0] * 50
mx = 0
sums = []
for i in range(n+1):
    for j in range(i+1,n+1):
        s = acc[j]-acc[i]
        sums.append(s)

# 最大の桁数
for d in range(50):
    if max(sums) & (1<<d):
        mx = max(mx, d)
        dp[d] += 1
mx = 0
for i in range(50):
    if dp[i] >= k:
        mx = max(mx,i)

# 計算
ans = 0
now = 0
for d in range(50,-1,-1):
    cnt = 0
    for s in sums:
        if s & (now+(1<<d)) == now+(1<<d):
            cnt += 1
    # print(d,cnt)
    if cnt >= k:
        now += 1<<d
print(now)
### BUGGY CODE ###

from itertools import count

for i in count(1):
    if i == "0":
        break
    else:
        print(i)

### FIXED CODE ###

from itertools import count

for i in count(1):
    s = input()

    if s == "0":
        break
    else:
        print("Case {}: {}".format(i, s))
### BUGGY CODE ###

from collections import deque

def BFS(x,y):
    dist = 1
    visited = deque()
    visited.append((x,y))
    destination = deque()
    search = [(1,0),(-1,0),(0,1),(0,-1)]
    for (dx,dy) in search:
        if maze[y+dy][x+dx] == ".":
            destination.append((x+dx,y+dy))
    same_dist = len(destination)
    moved = 0
    x = destination[0][0]
    y = destination[0][1]
    while destination:
        visited.append((x,y))
        destination.popleft()
        for (dx,dy) in search:
            if maze[y+dy][x+dx] == ".":
                if (x+dx,y+dy) not in destination and (x+dx,y+dy) not in visited:
                    destination.append((x+dx,y+dy))
        if len(destination) >= 1:
            x = destination[0][0]
            y = destination[0][1]
            moved += 1
            if moved == same_dist:
                dist += 1
                moved = 0
                same_dist = len(destination)
    return dist

H,W = map(int,input().split())
maze = [list("#"*(W+2))] + [list("#" + input() + "#") for i in range(H)] + [list("#"*(W+2))]
ans = 0

for y in range(1,H+1):
    for x in range(1,W+1):
        if maze[y][x] == ".":
            ans = max(ans,BFS(x,y))

print(ans)

### FIXED CODE ###

from collections import deque

def BFS(x,y):
    dist = 1
    visited = deque()
    visited.append((x,y))
    destination = deque()
    search = [(1,0),(-1,0),(0,1),(0,-1)]
    for (dx,dy) in search:
        if maze[y+dy][x+dx] == ".":
            destination.append((x+dx,y+dy))
    same_dist = len(destination)
    moved = 0
    x = destination[0][0]
    y = destination[0][1]
    while destination:
        visited.append((x,y))
        destination.popleft()
        for (dx,dy) in search:
            if maze[y+dy][x+dx] == ".":
                if (x+dx,y+dy) not in destination and (x+dx,y+dy) not in visited:
                    destination.append((x+dx,y+dy))
        if len(destination) >= 1:
            x = destination[0][0]
            y = destination[0][1]
            moved += 1
            if moved == same_dist:
                dist += 1
                moved = 0
                same_dist = len(destination)
    return dist

H,W = map(int,input().split())
maze = [list("#"*(W+2))] + [list("#" + input() + "#") for i in range(H)] + [list("#"*(W+2))]
ans = 0

for y in range(1,H+1):
    for x in range(1,W+1):
        if maze[y][x] == ".":
            ans = max(ans,BFS(x,y))

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

L,R = map(int,input().split())

rem = []
for i in range(L,R):
  for j in range(i+1,R+1):
    x = i % 2019
    y = j % 2019
    val = (x * y) % 2019
    rem.append(val)
    
print(min(rem))

### FIXED CODE ###

L,R = map(int,input().split())

if R - L > 2019:
  print(0)
else:
  minv = 2018 * 2018
  for i in range(L,R):
    for j in range(i+1,R+1):
      x = i % 2019
      y = j % 2019
      val = (x * y) % 2019
      if minv > val:
        minv = val
  print(minv)
### BUGGY CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
position = 0
for i in range(K):
    position = A[position]
    position -= 1

actual_position = position + 1
print(actual_position)

### FIXED CODE ###

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

    loop = {i: -1 for i in range(N)}
    loop[0] = 0
    position = 0

    for i in range(N + 1):
        position = A[position] - 1
        if loop[position] != -1:
            ini = loop[position]
            cycle = i + 1 - ini
            break
        else:
            loop[position] = i + 1

    M = (K - ini) % cycle

    answer = 0
    root = min(K, M + ini)
    for j in range(root):
        answer = A[answer] - 1

    answer += 1
    print(answer)

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

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

dp = [10**9]*(n+1)
dp[1] = 0

for i in range(2, n+1):
    for j in range(1, k+1):
        if i-j>0:
            dp[i] = min(dp[i], dp[i-j] + abs(hlist[i-1-j] - hlist[i-1]))
        else:
            break

print(dp[n])

### FIXED CODE ###

n, k = map(int, input().split())
heights = list(map(int, input().split()))
heights = [0] + heights
dp = [10**10]*(n+1)
dp[1] = 0

for i in range(1, n+1):
    for step in range(1, k+1):
        if (i + step) <= n:
            dp[i+step] = min(dp[i+step], abs(heights[i+step] - heights[i]) + dp[i])
print(dp[n])
### BUGGY CODE ###

n, k = map(int, input().split())
value = []
for _ in range(k):
    l, r = map(int, input().split())
    tmp = [i for i in range(l, r + 1)]
    value += tmp
value.sort()
mod = 998244353
dp = [0 for _ in range(n)]
dp[0] = 1
for i in range(n - 1):
    for dist in value:
        if i + dist <= n - 1:
            dp[i + dist] = (dp[i] + dp[i + dist]) % mod
print(dp[-1])

### FIXED CODE ###

mod = 998244353
n, k = map(int, input().split())
index_list = []
for _ in range(k):
    l, r = map(int, input().split())
    index_list.append([l, r])

dp = [0 for _ in range(n)]
dpsum = [0 for _ in range(n)]
dp[0] = 1
dpsum[0] = 1
for i in range(1, n):
    for l, r in index_list:
        l_index = max(i - r - 1, -1)
        r_index = i - l
        if r_index >= 0:
            dp[i] += dpsum[r_index]
            if (r_index > l_index) & (l_index >= 0):
                dp[i] -= dpsum[l_index]
    dp[i] = dp[i] % mod
    dpsum[i] = (dp[i] + dpsum[i - 1]) % mod
print(dp[-1])
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
d1, d2 = sorted([q for q in a if q > 0], reverse=True), sorted([q for q in a if q < 0])
C = 1000000007
if len(d1)+len(d2) < k:
    print(0)
elif k == n:
    ans = 1
    for q in a:
        ans = ans*q % C
    print(ans)
elif len(d1) == 0 and k % 2 == 0:
    ans = 1
    for q in range(k):
        ans = ans*d2[q] % C
    print(ans)
elif len(d1) == 0 and len(d2) < n:
    print(0)
elif len(d1) == 0:
    ans = 1
    for q in range(len(d2)-1, len(d2)-k-1, -1):
        ans = ans*d2[q] % C
    print(ans)
elif len(d2) == 0:
    ans = 1
    for q in range(k):
        ans = ans*d1[q] % C
    print(ans)
else:
    ans, now, w = 0, 0, min(k+1, len(d2)+1)
    for q in range(max(0, (k-len(d1)+1)//2*2), w, 2):
        if now == 0:
            now = 1
            for q1 in range(q):
                now *= d2[q1]
            for q1 in range(k-q):
                now *= d1[q1]
            ans = now
        else:
            now //= d1[k-q+1]*d1[k-q]
            now *= d2[q-2]*d2[q-1]
            ans = max(ans, now)
    print(ans % C)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
d1, d2 = sorted([q for q in a if q > 0], reverse=True), sorted([q for q in a if q < 0])
C = 1000000007
if len(d1)+len(d2) < k:
    print(0)
elif k == n:
    ans = 1
    for q in a:
        ans = ans*q % C
    print(ans)
elif len(d1) == 0 and k % 2 == 0:
    ans = 1
    for q in range(k):
        ans = ans*d2[q] % C
    print(ans)
elif len(d1) == 0 and len(d2) < n:
    print(0)
elif len(d1) == 0:
    ans = 1
    for q in range(len(d2)-1, len(d2)-k-1, -1):
        ans = ans*d2[q] % C
    print(ans)
elif len(d2) == 0:
    ans = 1
    for q in range(k):
        ans = ans*d1[q] % C
    print(ans)
else:
    ind = 0
    ans, now, w = 0, 0, min(k+1, len(d2)+1)
    for q in range(max(0, (k-len(d1)+1)//2*2), w, 2):
        if now == 0:
            """now = 1
            for q1 in range(q):
                now *= d2[q1]
            for q1 in range(k-q):
                now *= d1[q1]
            ans = now"""
            now, ind = 1, q
        else:
            if d1[k-q+1]*d1[k-q] <= d2[q-2]*d2[q-1]:
                ind = q
    ans = 1
    for q in range(ind):
        ans = ans*d2[q] % C
    for q in range(k-ind):
        ans = ans*d1[q] % C
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/24
Solved on 2019/3/
@author: shinjisu
"""


# ABC 056 C - Go Home
def getInt(): return int(input())
def zeros(n): return [0]*n
def zeros2(n, m): return [zeros(m) for i in range(n)] # obsoleted zeros((n, m))で代替
class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x


def prob():
    d = Debug()
    d.off()
    X = getInt()
    d.dmp((X), 'X')
    pos = [0]
    for i in range(1, 10*9+1):
        nextPos = []
        for a in pos:
            nextPos.append(a-i)
            nextPos.append(a)
            nextPos.append(a+i)
        pos = nextPos
        #d.dmp((pos), 'pos')
        if X in pos:
            break
    return i


ans = prob()
if ans is None:
    pass
elif type(ans) == tuple and ans[0] == 1:  # 1,ans
    for elm in ans[1]:
        print(elm)
else:
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/3/24
Solved on 2019/3/
@author: shinjisu
"""


# ABC 056 C - Go Home
def getInt(): return int(input())
def zeros(n): return [0]*n
def zeros2(n, m): return [zeros(m) for i in range(n)] # obsoleted zeros((n, m))で代替
class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x


def prob():
    d = Debug()
    d.off()
    X = getInt()
    d.dmp((X), 'X')
    sm = 0
    for i in range(1, 10**9+1):
        sm += i
        if X <= sm:
            break
    return i


ans = prob()
if ans is None:
    pass
elif type(ans) == tuple and ans[0] == 1:  # 1,ans
    for elm in ans[1]:
        print(elm)
else:
    print(ans)