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

from collections import defaultdict,deque

H, W = map(int, input().split())
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S[0] -= 1
S[1] -= 1
G[0] -= 1
G[1] -= 1
c = [input() for i in range(H)]
dist = [[-1]*W for _ in range(H)]

for i in range(H):
    for g in range(W):
        if c[i][g] == "#":
            dist[i][g] = -2

checkList = set()
que = deque()
que.append(S)
dist[S[0]][S[1]] = 0

directions = [(0, -1), (0, 1), (1, 0), (-1, 0)]

cost = 0
count = 0

while True:
    count += 1
    if count >= 10**7:
        print("あああああ")
        break
    if len(que) == 0:
        cost += 1
        que = set()
        for h, w in checkList:
            for i in range(-2, 3):
                for g in range(-2, 3):
                    nh = h+i
                    nw = w+g
                    if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                        continue
                    else:
                        if dist[nh][nw] == -1:
                            que.add((nh, nw))
        que = deque(que)
        checkList = set()
        if len(que) == 0:
            print(-1)
            exit()
    else:
        h, w = que.popleft()
        if h == G[0] and w == G[1]:
            print(cost)
            exit()
        for i in range(4):
            nh = h+directions[i][0]
            nw = w+directions[i][1]
            if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                continue
            if dist[nh][nw] == -1:
                que.append((nh, nw))
                dist[nh][nw] = cost
            elif dist[nh][nw] == -2:
                checkList.add((h, w))

### FIXED CODE ###

from collections import defaultdict,deque

H, W = map(int, input().split())
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S[0] -= 1
S[1] -= 1
G[0] -= 1
G[1] -= 1
c = [input() for i in range(H)]
dist = [[-1]*W for _ in range(H)]

for i in range(H):
    for g in range(W):
        if c[i][g] == "#":
            dist[i][g] = -2

checkList = set()
que = deque()
que.append(S)

directions = [(0, -1), (0, 1), (1, 0), (-1, 0)]

cost = 0

while True:
    if len(que) == 0:
        cost += 1
        que = set()
        for h, w in checkList:
            for i in range(-2, 3):
                for g in range(-2, 3):
                    nh = h+i
                    nw = w+g
                    if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                        continue
                    else:
                        if dist[nh][nw] == -1:
                            que.add((nh, nw))
        que = deque(que)
        checkList = set()
        if len(que) == 0:
            print(-1)
            exit()
    else:
        h, w = que.popleft()
        dist[h][w] = cost
        if h == G[0] and w == G[1]:
            print(cost)
            exit()
        for i in range(4):
            nh = h+directions[i][0]
            nw = w+directions[i][1]
            if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                continue
            if dist[nh][nw] == -1:
                que.append((nh, nw))
                dist[nh][nw] = cost
            elif dist[nh][nw] == -2:
                checkList.add((h, w))
### BUGGY CODE ###

import sys
from math import sqrt
def input():
	return sys.stdin.readline()[:-1]

import heapq
class DijkstraMatrix():
	#隣接行列版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, matrix, start):
		self.matrix = matrix
		self.start = start
		self.size = len(matrix)

	def solve(self):
		self.dist = [float("inf") for _ in range(self.size)]
		self.dist[self.start] = 0
		self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
				#これいる？
			for v in range(self.size):
				w = self.matrix[u][v]
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))

			self.cnt += 1

		return

	def distance(self, goal):
		return self.dist[goal]

	def path(self, goal):
		self.path = [goal]
		while self.path[-1] != self.start:
			self.path.append(self.prev[self.path[-1]])
		return self.path[::-1]

xs, ys, xt, yt = map(int, input().split())
n = int(input())
b = [[xs, ys, 0], [xt, yt, 0]] + [list(map(int, input().split())) for _ in range(n)]
d = [[float("inf") for _ in range(n+2)] for _ in range(n+2)]

for i in range(n+2):
	for j in range(n+2):
		if i != j:
			d[i][j] = max(sqrt((b[i][0] - b[j][0])**2 + (b[i][1] - b[j][1])**2) - b[i][2] - b[j][2], 0)

dijkstra = DijkstraMatrix(d, 0)
dijkstra.solve()
print(dijkstra.distance(1))

### FIXED CODE ###

import sys
from math import sqrt
def input():
	return sys.stdin.readline()[:-1]

import heapq
class DijkstraMatrix():
	#隣接行列版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, matrix, start):
		self.matrix = matrix
		self.start = start
		self.size = len(matrix)

	def solve(self):
		self.dist = [float("inf") for _ in range(self.size)]
		self.dist[self.start] = 0
		self.prev = [-1 for _ in range(self.size)]
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
				#これいる？
			for v in range(self.size):
				w = self.matrix[u][v]
				if self.dist[v] > u_dist + w:
					self.dist[v] = u_dist + w
					self.prev[v] = u
					heapq.heappush(self.q, (self.dist[v], v))

			self.cnt += 1

		return

	def distance(self, goal):
		return self.dist[goal]

	def path(self, goal):
		self.path = [goal]
		while self.path[-1] != self.start:
			self.path.append(self.prev[self.path[-1]])
		return self.path[::-1]

xs, ys, xt, yt = map(int, input().split())
n = int(input())
b = [[xs, ys, 0], [xt, yt, 0]] + [list(map(int, input().split())) for _ in range(n)]
d = [[float("inf") for _ in range(n+2)] for _ in range(n+2)]

for i in range(n+2):
	for j in range(n+2):
		if i != j:
			d[i][j] = max(sqrt((b[i][0] - b[j][0])**2 + (b[i][1] - b[j][1])**2) - b[i][2] - b[j][2], 0)

dijkstra = DijkstraMatrix(d, 0)
dijkstra.solve()
print(dijkstra.distance(1))
### BUGGY CODE ###

x , y ,z , k = map(int, input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = []
for p in a:
    for q in b:
        for r in c:
            ans.append(p+q+r)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

### FIXED CODE ###

x , y ,z , k = map(int, input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

e = [i + j for i in a[:k] for j in b[:k]]
e.sort(reverse=True)
e = e[:k]
ans = [i + j for i in e for j in c[:k]]
ans.sort(reverse=True)

for i in range(k):
    print(ans[i])
### BUGGY CODE ###

from bisect import bisect
from collections import defaultdict
def main():
	n, k = map(int, input().split())
	*a, = map(int, input().split())
	idx = defaultdict(list)
	for i, x in enumerate(a):
		idx[x].append(i)
	m = (k * n).bit_length()
	dub = [[0] * n for _ in range(m)]
	for i, x in enumerate(a):
		if i == idx[x][-1]:
			dub[0][i] = n + idx[x][0] - i
		else:
			dub[0][i] = idx[x][bisect(idx[x], i)] - i
	# print(dub[0])
	for i in range(m - 1):
		for j in range(n):
			dub[i + 1][j] = dub[i][j] + 1 + dub[i][(j + dub[i][j] + 1) % n]
	# print(dub)
	now = -1
	for i in range(m - 1, -1, -1):
		if now + 1 + dub[i][(now + 1) % n] < n * k:
			now += 1 + dub[i][(now + 1) % n]
	# print(now)
	if now == n * k:
		print("")
		exit()
	b = a[(now + 1) % n:]
	# print(b)
	inQ = {x: False for x in b}
	Q = []
	for x in b:
		if inQ[x]:
			while Q[-1] != x:
				inQ[Q.pop()] = False
			Q.pop()
			inQ[x] = False
		else:
			inQ[x] = True
			Q.append(x)
	print(" ".join(map(str, Q)))

if __name__ == '__main__':
	main()


### FIXED CODE ###

from bisect import bisect
from collections import defaultdict
def main():
	n, k = map(int, input().split())
	*a, = map(int, input().split())
	idx = defaultdict(list)
	for i, x in enumerate(a):
		idx[x].append(i)
	m = (k * n).bit_length()
	dub = [[-1] * n for _ in range(m)]
	for i, x in enumerate(a):
		if i == idx[x][-1]:
			dub[0][i] = n + idx[x][0] - i
		else:
			dub[0][i] = idx[x][bisect(idx[x], i)] - i
	# print(dub[0])
	for i in range(m - 1):
		for j in range(n):
			if dub[i][j]<n*k and dub[i][j]!=-1:
				dub[i + 1][j] = dub[i][j] + 1 + dub[i][(j + dub[i][j] + 1) % n]
	# print(dub)
	now = -1
	for i in range(m - 1, -1, -1):
		if dub[i][(now+1)%n]!=-1 and now + 1 + dub[i][(now + 1) % n] < n * k:
			now += 1 + dub[i][(now + 1) % n]
	# print(now)
	if now == n * k:
		print("")
		exit()
	b = a[(now + 1) % n:]
	# print(b)
	inQ = {x: False for x in b}
	Q = []
	for x in b:
		if inQ[x]:
			while Q[-1] != x:
				inQ[Q.pop()] = False
			Q.pop()
			inQ[x] = False
		else:
			inQ[x] = True
			Q.append(x)
	print(" ".join(map(str, Q)))

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

N, W = map(int, input().rstrip().split(' '))
weight_lst = [0 for i in range(W+1)]

for _ in range(N):
  w, v = map(int, input().rstrip().split(' '))
  weight_lst2 = weight_lst.copy()
  for i in range(w, W+1):
    weight_lst2[i] = max(weight_lst[i-w]+v, weight_lst[i])
  weight_lst = weight_lst2
print(weight_lst[-1])

### FIXED CODE ###

import numpy as np
N, W = map(int, input().rstrip().split(' '))
weight_array = np.zeros(W+1)

for _ in range(N):
  w, v = map(int, input().rstrip().split(' '))
  weight_array[w:] = np.maximum(weight_array[:-w]+v, weight_array[w:])
print(int(weight_array[-1]))
### BUGGY CODE ###

a,b,n = map(int,input().split())
#(a*x)//b - a*(x//b) の最大値を求める
ax_list = [a*i for i in range(1,n+1)]
if b > n:
    # ax//b だけ考えればいい
    print(a*n//b)
else:
    # ax//b か　bより大きいx で探す
    x = 2*b-1
    first = a*(b-1)//b
    second = (a*x)//b - a*(x//b)
    print(first if first >= second else second)

### FIXED CODE ###

a,b,n = map(int,input().split())
#(a*x)//b - a*(x//b) の最大値を求める
if b > n:
    # ax//b だけ考えればいい
    print(a*n//b)
else:
    # ax//b か　bより大きいx で探す
    x = 2*b-1
    first = a*(b-1)//b
    second = (a*x)//b - a*(x//b)
    print(first if first >= second else second)
### BUGGY CODE ###

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

list_a = list(set(a))

result = 0
for i in list_a:
    cnt = a.count(i)
    if cnt != i:
        result = result + cnt if cnt < i else result + cnt - i

print(result)


### FIXED CODE ###

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

count_a = {}
for n in range(N):
    if a[n] in count_a.keys():
        count_a[a[n]] += 1
    else:
        count_a[a[n]] = 1

result = 0
for n in list(count_a.keys()):
    if count_a[n] != n:
        result = result + count_a[n] if count_a[n] < n else result + count_a[n] - n

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

N, W = list(map(lambda x: int(x), input().split()))

wV = [list(map(lambda x: int(x), input().split())) for _ in range(N)]

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
	for j in range(W + 1):
		if j + wV[i][0] <= W:
			dp[i + 1][j + wV[i][0]] = dp[i][j] + wV[i][1]
		
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
		
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())

dp = [0] * (W+1)
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        a = dp[j-w]+v
        if dp[j] < a:
            dp[j] = a

print(dp[W])
### BUGGY CODE ###

import math
A, B, N = map(int, input().split())

d = 0
ans = 0
# for i in range(1, N+1):
#     d = math.floor((A*i)/B) - A*math.floor(i/B)
#     if ans <= d:
#         ans = d
#     else:
#         print(ans)
#         exit()
#
# print(ans)

mid = N//2
if (math.floor((A*mid)/B) - A*math.floor(mid/B)) < (math.floor((A*(mid+1))/B) - A*math.floor((mid+1)/B)):
    for i in range(mid, N+1):
        d = math.floor((A * i) / B) - A * math.floor(i / B)
        if ans <= d:
            ans = d
        else:
            print(ans)
            exit()
else:
    for i in range(0, mid+1):
        d = math.floor((A * i) / B) - A * math.floor(i / B)
        if ans <= d:
            ans = d
        else:
            print(ans)
            exit()

print(ans)

### FIXED CODE ###

import math

A, B, N = map(int, input().split())
print(math.floor((A * min(B-1, N)) / B) - A * math.floor(min(B-1, N) / B))
### BUGGY CODE ###

n=int(input())
f=0
c=0
while n>0:
  c=n%10
  if c==7:
    f=1
    print("Yes")
if f==0:
  print("No")
  

### FIXED CODE ###

n=int(input())
f=0
while n>0:
      c=n%10
      if  c==7:
            f=1
            print("Yes")
            break
      n=int(n/10)
if f==0:
      print("No")
### BUGGY CODE ###

from functools import cmp_to_key
n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
d.sort(key = cmp_to_key(lambda x, y: y[1] / y[0] - x[1] / x[0]))
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        for k in list(t.keys()):
          if k <= nw and t[k] < nv:
            del t[k]
        t[nw] = nv
    else:
      Flag = False
      for k in t:
        if nw <= k and nv <= t[k]:
          Flag = True
          break
      if Flag:
        continue
      for k in list(t.keys()):
        if k <= nw and t[k] < nv:
          del t[k]
      t[nw] = nv
        
print(max(t.values()))


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

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

for i in range(1,N+1):
    print(A.count(i))


### FIXED CODE ###

N = int(input())
A = input().split()

import collections
c = collections.Counter(A)

for i in range(1,N+1):
    print(c[str(i)])
### BUGGY CODE ###

h, n = map(int, input().split())
a = []
b = []
for i in range(n):
    a_tmp, b_tmp = map(int, input().split())
    a.append(a_tmp)
    b.append(b_tmp)

a_max = 10000
dp_max = 100000000
dp = [dp_max] * (h + a_max + 1)
dp[0] = 0

for i in range(h):
    if dp[i] == dp_max:
        continue
    for j in range(n):
        a_current = a[j]
        b_current = b[j]
        if dp[i] + b_current < dp[i + a_current]:
            dp[i + a_current] = dp[i] + b_current

dp_min = dp_max
for i in range(h, h + a_max + 1):
    if dp[i] < dp_min:
        dp_min = dp[i]

print(dp_min)

### FIXED CODE ###

h, n = map(int, input().split())
a = []
b = []
for i in range(n):
    a_tmp, b_tmp = map(int, input().split())
    a.append(a_tmp)
    b.append(b_tmp)

a_max = 10000
dp_max = 100000000
dp = [dp_max] * (h + a_max + 1)
dp[0] = 0

for i in range(h):
    if dp[i] == dp_max:
        continue
    for j in range(n):
        a_current = a[j]
        b_current = b[j]
        if dp[i] + b_current < dp[i + a_current]:
            dp[i + a_current] = dp[i] + b_current

dp_min = dp_max
for i in range(h, h + a_max + 1):
    if dp[i] < dp_min:
        dp_min = dp[i]

print(dp_min)
### BUGGY CODE ###

import sys
import itertools
N=int(input())
L=list(map(int,input().split()))
L.sort(reverse=True)

comb=itertools.combinations(L,2)
comb=list(comb)
total=0
for c in comb:
    s = c[0] - c[1]
    for l in L:
        if(l > s and c[1] > l):
            total+=1
print(total)

### FIXED CODE ###

import sys
from bisect import bisect_left
N=int(input())
L=list(map(int,input().split()))
L.sort()
total = 0
for i in range(N):
  for j in range(i + 1, N):
    a = L[i] + L[j]
    total += max(bisect_left(L, a) - j - 1, 0)

print(total)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
mod = 7 + 10 ** 9

def Pow(i, n):
    if n == 0:
        return 1
    else:
        ans = Pow(i * i % mod, n//2)
        if n % 2 == 1:
            ans *= i
            ans %= mod
        return ans

Nfact = [1]
NfactRev = [1]
for i in range(1, N+2):
    Nfact.append((Nfact[i-1] * (i)) % mod)
    NfactRev.append((NfactRev[i-1] * Pow(i, mod - 2)) % mod)
    if A.count(i) == 2:
        Double = [j for j, x in enumerate(A) if x == i]

doublearray = N - (Double[1] - Double[0])
for i in range(1, N+2):
    whole = Nfact[N+1] * NfactRev[N+1-i] * NfactRev[i] % mod
    if i <= doublearray+1:
        double = Nfact[doublearray] * NfactRev[doublearray-i+1] * NfactRev[i-1] % mod
    else:
        double = 0
    print(whole - double)

### FIXED CODE ###

def Pow(i, n):
    if n == 0:
        return 1
    else:
        ans = Pow(i * i % mod, n//2)
        if n % 2 == 1:
            ans *= i
            ans %= mod
        return ans

N = int(input())
A = [int(i) for i in input().split()]
mod = 7 + 10 ** 9
num = [-1 for i in range(N)]
for i, a in enumerate(A):
    if num[a-1] == -1:
        num[a-1] = i
    else:
        Double = [num[a-1], i]

Nfact = [1]
for i in range(1, N+2):
    Nfact.append((Nfact[i-1] * (i)) % mod)
NfactRev = [Pow(Nfact[N+1], mod-2)]
for i in range(1, N+1):
    NfactRev.append(NfactRev[i-1] * (N+2-i) % mod)
NfactRev.append(1)
NfactRev.reverse()

doublearray = N + 1 - (Double[1] - Double[0])
for i in range(1, N+2):
    whole = Nfact[N+1] * NfactRev[N+1-i] * NfactRev[i] % mod
    if i <= doublearray:
        double = Nfact[doublearray-1] * NfactRev[doublearray-i] * NfactRev[i-1] % mod
    else:
        double = 0
    print((whole - double) % mod)
### BUGGY CODE ###

def f_d():
    n = int(input())
    c = 0
    for i in range(1, n):
        c += i
    print(c)

if __name__ == "__main__":
    f_d()


### FIXED CODE ###

def f_d():
    n = int(input())
    n -= 1
    if n%2==0:
        print(n*((n-2)//2+1)+n//2)
    else:
        print(n*((n-1)//2+1))

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

# -*- coding: utf-8 -*-
"""
Created on Sun Oct  7 22:06:12 2018
ABC073D
@author: maezawa
"""
import itertools as itr
import sys
input = sys.stdin.readline

n, m, r = list(map(int, input().split()))
rarray = list(map(int, input().split()))
adjmatrix = [[10**10]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    adjmatrix[i][i] = 0
    
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if adjmatrix[a][b] > c:
        adjmatrix[a][b] = c
        adjmatrix[b][a] = c

#print(abc)

# Warshall-Floyd Algorithm
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            adjmatrix[i][j] = min([adjmatrix[i][j],
                      adjmatrix[i][k] + adjmatrix[k][j]])
            #adjmatrix[j][i] = adjmatrix[i][j]
        
#print(*adjmatrix, sep='\n')
    
# search for ri to rj
mincnt = 10*10
for route in itr.permutations(rarray):
    cnt = 0
    for i in range(len(rarray)-1):
        cnt += adjmatrix[route[i]][route[i+1]]
    if cnt < mincnt:
        mincnt = cnt

print(mincnt)
        
        

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Oct  8 10:17:39 2018

@author: maezawa
"""

import math
from itertools import permutations

#フロイド・ワーシャル
def warshall_floyd(glath):
	
	for k in range(len(glath)):
		for i in range(len(glath)):
			for j in range(len(glath[i])):
				if glath[i][j] > glath[i][k] + glath[k][j]:
                                   glath[i][j] = glath[i][k] + glath[k][j]
                                   glath[j][i] = glath[i][k] + glath[k][j]				
	return glath

N, M ,R= [int(x) for x in str(input()).split()]  #グラフの大きさ 
r=[int(x) for x in str(input()).split()]
graph=[[float("inf")]*N for i in range(N)]


for i in range(M):
	a,b,c=[int(x) for x in str(input()).split()]
	#if a in r and b in r:
	graph[a-1][b-1]=c
	graph[b-1][a-1]=c

#all_cost=warshall_floyd(select_graph)
all_cost=warshall_floyd(graph)


max_count=float("inf")
for i in permutations(r):
        cost=0
        for j in range(len(i)-1):                
                cost+= all_cost[i[j]-1][i[j+1]-1]       
        max_count=min(max_count,cost)

print(max_count)
### BUGGY CODE ###

#At coder 2020/2/9 B

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

ans='YES'
for ii in range(N-1):
    for jj in range(ii+1,N):
        if A[ii]==A[jj]:
            ans='NO'
            break
    if ans=='NO':
        break


print(ans)

### FIXED CODE ###

#At coder 2020/2/9 B

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

if len(A)-len(set(A))==0:
    ans='YES'
else:
    ans='NO'
#ans='YES'
#for ii in range(N-1):
#    for jj in range(ii+1,N):
#        if A[ii]==A[jj]:
#            ans='NO'
#            break
#    if ans=='NO':
#        break


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

from sys import stdin, stdout 
n,k=map(int,input().split())
a=[int(o) for o in input().split()]
prod=1
for i in range(k):
    prod*=a[i]
for i in range(k,n):
    prev=prod
    prod//=a[i-k]
    prod*=a[i]
    if prod>prev: stdout.write("Yes\n")
    else: stdout.write("No\n")


### FIXED CODE ###

from sys import stdin, stdout 
n,k=map(int,input().split())
a=[int(o) for o in input().split()]
prod=1
for i in range(k,n):
    prev=a[i-k]
    if a[i]>prev: stdout.write("Yes\n")
    else: stdout.write("No\n")
### BUGGY CODE ###

from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


memo = {}

def nxt(x):
    i = 0
    cnt = 0
    while x >= 1<<i:
        if x & (1<<i):
            cnt += 1
        i += 1
    return x % cnt


def count(x):
    s = 0
    a = [x]
    while x != 0:
        s += 1
        x = nxt(x)
        if x in memo:
            s = s + memo[x]
            break
        a.append(x)
    for i in range(len(a)):
        memo[a[i]] = s - i
    return s

def main():
    n = int(input())
    x = input()
    x = int(x, 2)
    for i in range(n):
        y = x ^ (1<<(n-i-1))
        s = count(y)
        print(s)


main()


### FIXED CODE ###

from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


memo = {}

def countbit(x):
    i = 0
    cnt = 0
    while x >= 1<<i:
        if x & (1<<i):
            cnt += 1
        i += 1
    return cnt


def count(x):
    # if c == 0:
    #     return 0
    # s = 1
    # x = x % c
    s = 0
    while x != 0:
        s += 1
        x = x % countbit(x)
    return s

def main():
    n = int(input())
    xs = list(input())
    c = len([i for i in xs if i == '1'])
    dp = {}
    dps = {}
    for i in range(-1, 2):
        cc = c + i
        if cc == 0:
            continue
        dp[cc] = [-1] * n
        base = 1 % cc
        dpstmp = 0
        for i in range(n):
            dp[cc][i] = base
            if xs[-i-1] == '1':
                dpstmp += base
            base = base * 2 % cc
        dps[cc] = dpstmp % cc

    for i in range(n):
        cc = c
        if xs[i] == '1':
            cc -= 1
        else:
            cc += 1
        if cc == 0:
            print(0)
            continue
        res = dps[cc]
        if xs[i] == '1':
            res = (res - dp[cc][-i-1]) % cc
        else:
            res = (res + dp[cc][-i-1]) % cc
        s = count(res) + 1
        print(s)


main()