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

#### 132_E

import queue
import sys
sys.setrecursionlimit(300000)
 
n,m=map(int,input().split())

edges=[[] for i in range(3*n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    u0,u1,u2=u,u+n,u+2*n
    v0,v1,v2=v,v+n,v+2*n
    edges[u0].append(v1)
    edges[u1].append(v2)
    edges[u2].append(v0)
    
s,t=map(int,input().split())
s,t=s-1,t-1
    
def bfs(s,t):
    que=queue.Queue()
    que.put(s)
    d[s]=0
    visit[s]=True
    while not que.empty():
        q=que.get()
        if q==t:
            return d[t]
        for z in edges[q]:
            if visit[z]==False:
                que.put(z)
                d[z]=d[q]+1
                visit[z]=True
    return d[t]
                
visit=[False for _ in range(3*n)]
d=[-1 for _ in range(3*n)]

print(bfs(s,t)//3)

### FIXED CODE ###

#### 132_E

import queue
import sys
sys.setrecursionlimit(300000)
 
n,m=map(int,input().split())

edges=[[] for i in range(3*n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    u0,u1,u2=u,u+n,u+2*n
    v0,v1,v2=v,v+n,v+2*n
    edges[u0].append(v1)
    edges[u1].append(v2)
    edges[u2].append(v0)
    
s,t=map(int,input().split())
s,t=s-1,t-1
    
def bfs(s,t):
    que=queue.Queue()
    que.put(s)
    d[s]=0
    visit[s]=True
    while not que.empty():
        q=que.get()
        if q==t:
            return d[t]
        for z in edges[q]:
            if visit[z]==False:
                que.put(z)
                d[z]=d[q]+1
                visit[z]=True
    return d[t]
                
visit=[False for _ in range(3*n)]
d=[-1 for _ in range(3*n)]

print(bfs(s,t)//3)
### BUGGY CODE ###

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

MOD = 998244353
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
dd = []
for i in range(n):
	x, y = map(int, input().split())
	dd.append((x, y, i))
d = [[-1, -1] for _ in range(n)]
dd.sort()
for i, x in enumerate(dd):
	d[x[2]][0] = i+1
dd.sort(key=lambda x: x[1])
for i, x in enumerate(dd):
	d[x[2]][1] = i+1
d.sort()
d = [(x[0], x[1]) for x in d]
lu = [0 for _ in range(n)]
ld = [0 for _ in range(n)]
rd = [0 for _ in range(n)]
ru = [0 for _ in range(n)]
bitl, bitr = BIT(n), BIT(n)

for i in range(n):
	x = d[i][1]
	s = bitl.Sum(x)
	lu[i] = i - s
	ld[i] = s
	bitl.PointAdd(x, 1)

for i in range(n-1, -1, -1):
	x = d[i][1]
	s = bitr.Sum(x)
	ru[i] = n-1-i - s
	rd[i] = s
	bitr.PointAdd(x, 1)
#print(lu, ld, rd, ru, sep="\n")

ans = (n*pow(2, n, MOD) - n) % MOD
for i in range(n):
	ans -= pow(2, lu[i]+ld[i], MOD) + pow(2, ld[i]+rd[i], MOD) + pow(2, rd[i]+ru[i], MOD) + pow(2, ru[i]+lu[i], MOD)
	ans += pow(2, lu[i], MOD) + pow(2, ld[i], MOD) + pow(2, rd[i], MOD) + pow(2, ru[i], MOD)
	ans %= MOD

print(ans)


### FIXED CODE ###

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

MOD = 998244353
class Rsum():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = 0
		while L<R:
			if R & 1:
				R -= 1
				s += self.node[R-1]
			if L & 1:
				s += self.node[L-1]
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
d = []
for i in range(n):
	x, yy = map(int, input().split())
	d.append((x, yy, i))
y = [-1 for _ in range(n)]
d.sort(key=lambda x: x[1])
for i, x in enumerate(d):
	y[x[2]] = i

d.sort()
lus = [-1 for _ in range(n)]
lds = [-1 for _ in range(n)]
rus = [-1 for _ in range(n)]
rds = [-1 for _ in range(n)]

st = Rsum(n)
for i in range(n):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	lus[i] = g
	lds[i] = i - g
	st.Add(pnt, 1)

st = Rsum(n)
for i in range(n-1, -1, -1):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	rus[i] = g
	rds[i] = n-1-i - g
	st.Add(pnt, 1)

pws = [1]
for _ in range(n-1):
	pws.append((pws[-1] * 2) % MOD)

ans = (n * pws[n-1]) % MOD
for lu, ld, ru, rd in zip(lus, lds, rus, rds):
	ans += ((pws[lu]-1) * (pws[rd]-1))
	ans += ((pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[rd]-1))
	ans += ((pws[lu]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[ld]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1) * (pws[rd]-1))
	ans %= MOD
print(ans)
### BUGGY CODE ###

N , Ma, Mb = map(int, input().split())

a = [0] * N
b = [0] * N
c = [0] * N

for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())

# 最小値を求める問題なのでinfで初期化
# dp[i][sun_a][sum_b]で考えていく
dp = [[[float('inf') for _ in range(10 * N + 1)] for _ in range(10 * N + 1)] for _ in range(N+1)]

# 初期選択状態を0とする

dp[0][0][0] = 0
for i in range(N):
    for j in range(10*N+1):
        for k in range(10*N+1):
            if dp[i][j][k] == float('inf'):
                continue
            
            # 選ばなかった場合
            dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
            # 選んだ場合
            dp[i+1][j+a[i]][k+b[i]] = min(dp[i+1][j+a[i]][k+b[i]], dp[i][j][k] + c[i])


ans = float('inf')
# 0スタートは何を選んでいない状態となり最小値が0になってしまうため1から開始する
for i in range(1,10 * N + 1):
    for j in range(1,10 * N + 1):
        if i * Mb != j * Ma:
            continue
        ans = min(ans, dp[N][i][j])

if ans == float('inf'):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N , Ma, Mb = map(int, input().split())

a = [0] * N
b = [0] * N
c = [0] * N

for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())

# TLEになってしまうためinfを5000とかで設定する
INF = 5000

# 最小値を求める問題なのでinfで初期化
# dp[i][sun_a][sum_b]で考えていく
dp = [[[INF for _ in range(10 * N + 1)] for _ in range(10 * N + 1)] for _ in range(N+1)]

# 初期選択状態を0とする

dp[0][0][0] = 0
for i in range(N):
    for j in range(10*N+1):
        for k in range(10*N+1):
            if dp[i][j][k] == INF:
                continue
            
            # 選ばなかった場合
            dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
            # 選んだ場合
            dp[i+1][j+a[i]][k+b[i]] = min(dp[i+1][j+a[i]][k+b[i]], dp[i][j][k] + c[i])


ans = INF
# 0スタートは何を選んでいない状態となり最小値が0になってしまうため1から開始する

# TLEになったため変更
#for i in range(1,10 * N + 1):
#    for j in range(1,10 * N + 1):
#        if i * Mb != j * Ma:
#            continue
#        ans = min(ans, dp[N][i][j])
#

for i in range(1, 10*N+1):
        if i*Ma>10*N or i*Mb>10*N:
            break
        ans = min(ans, dp[N][i*Ma][i*Mb])

if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N = int(input())
S = input().strip()
cnt = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            cur = [i,j,k]
            ind = 0
            for n in range(N):
                if int(S[n])==cur[ind]:
                    ind += 1
                    if ind==3:
                      cnt += 1
                      break
print(cnt)


### FIXED CODE ###

N = int(input())
S = list(map(int,list(input().strip())))
cnt = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            cur = [i,j,k]
            ind = 0
            for n in range(N):
                if S[n]==cur[ind]:
                    ind += 1
                    if ind==3:
                        cnt += 1
                        break
print(cnt)
### BUGGY CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7
dp = [[0] * 13 for i in range(N + 1)]
dp[0][0] = 1

for i, s in enumerate(S[::-1], start=1):
    p10 = 10 ** (i - 1)
    if s != '?':
        for k in range(13):
            dp[i][(int(s) * p10 + k) % 13] += dp[i - 1][k]
            dp[i][(int(s) * p10 + k) % 13] %= MOD
    else:
        for j in range(10):
            for k in range(13):
                dp[i][(j * p10 + k) % 13] += dp[i - 1][k]
                dp[i][(j * p10 + k) % 13] %= MOD

print(dp[N][5] % MOD)


### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7
dp = [[0] * 13 for i in range(N + 1)]
dp[0][0] = 1

for i, s in enumerate(S[::-1], start=1):
    p10 = pow(10, i - 1, 13)
    if s != '?':
        for k in range(13):
            dp[i][(int(s) * p10 + k) % 13] += dp[i - 1][k]
            dp[i][(int(s) * p10 + k) % 13] %= MOD
    else:
        for j in range(10):
            for k in range(13):
                dp[i][(j * p10 + k) % 13] += dp[i - 1][k]
                dp[i][(j * p10 + k) % 13] %= MOD

print(dp[N][5] % MOD)
### BUGGY CODE ###

n = int(input())
A=list(map(int,input().split()))
cnt=0
import numpy as np
table=np.array([[0]*(n+1) for i in range(n)])
B=[]
C=[]
for i,a in enumerate(A):
    B.append(A[i]+i)
    C.append(A[i]-i)
from collections import Counter
Bd=dict(Counter(B))
Cd=dict(Counter(C))
cnt=0
for k in Bd.keys():
    try:
        cnt+=Bd[k]*Cd[-k]
    except KeyError:
        continue
print(cnt)

### FIXED CODE ###

n = int(input())
A=list(map(int,input().split()))
cnt=0
B=[]
C=[]
for i,a in enumerate(A):
    B.append(A[i]+i)
    C.append(A[i]-i)
from collections import Counter
Bd=dict(Counter(B))
Cd=dict(Counter(C))
cnt=0
for k in Bd.keys():
    try:
        cnt+=Bd[k]*Cd[-k]
    except KeyError:
        continue
print(cnt)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

S = readline().rstrip()
S = S[::-1]
dp = [0]*13
dp[0] = 1
pow10 = 4
for i,s in enumerate(S):
    dpnew = [0]*13
    pow10 = pow10*10%13
    if s != '?':
        k = int(s)
        for j in range(13):
            dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    else:
        for k in range(10):
            for j in range(13):
                dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    dp = dpnew

print(dp[5])


### FIXED CODE ###

import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

S = readline().rstrip()
S = S[::-1]
dp = [0]*13
dp[0] = 1

for i,s in enumerate(S):
    dpnew = [0]*13
    pow10 = pow(10,i,13)
    if s != '?':
        k = int(s)
        for j in range(13):
            dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    else:
        for k in range(10):
            for j in range(13):
                dpnew[(k*pow10+j)%13] = (dpnew[(k*pow10+j)%13]+dp[j])%mod
    dp = dpnew

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

def Eratosthenes(n):
	N = [1 for i in range(0,n+1)]
	i = 3
	while i*i<=n:
		if N[i]:
			j = i*i
			while j<=n:
				N[j] = 0
				j += i*2
		i += 2
	return N

while True:
	N = Eratosthenes(999999)
	try:
		n = int(input())
	except EOFError:
		break
	cnt = 0
	if n>=2:
		cnt = 1
	for i in range(3, n+1, 2):
		cnt += N[i]
	print(cnt)

### FIXED CODE ###

def Eratosthenes(n):
	N = [1 for i in range(0,n+1)]
	i = 3
	while i*i<=n:
		if N[i]:
			j = i*i
			while j<=n:
				N[j] = 0
				j += i*2
		i += 2
	return N

N = Eratosthenes(999999)
while True:
	try:
		n = int(input())
	except EOFError:
		break
	cnt = 0
	if n>=2:
		cnt = 1
	for i in range(3, n+1, 2):
		cnt += N[i]
	print(cnt)
### BUGGY CODE ###

import sys
import numpy as np

def main():
    n = int(input())
    A_ = [int(x) for x in input().split()]
    A = [a for a in A_ if a != 0]
    N = len(A)

    mod = 10**9+7
    PR = 2
    order = [1]
    x = PR
    while x != 1:
        order.append(x)
        x *= PR
        x %= mod

    order_l = len(order)
    where = np.zeros(mod, int)
    for i in range(order_l):
        where[order[i]] = i
    prevCnt = np.zeros(mod, int)
    resCnt = np.zeros(mod, int)
    for n in range(N):
        if A[n] != 0:
            prevCnt[where[A[n]]] += 1
            resCnt[(A[n] * A[n]) % mod ] -= 1
    N_=1
    while N_ < 2*len(prevCnt): N_ *= 2
    nf = np.zeros(N_,int)
    nf[:len(prevCnt)]=prevCnt
    nf=np.fft.rfft(nf)
    fftRes = np.rint( np.fft.irfft(nf*nf))
    for r in range(len(fftRes)):
        if fftRes[r] != 0:
            resCnt[order[r % order_l]] += fftRes[r]
    ans = 0
    for p in range(mod):
        if resCnt[p] != 0:
            ans += (resCnt[p] // 2) * p
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    mod = 10**9+7
    a_sum = sum(A)
    a_cum = [0] * (n+1)
    for i in range(n):
        a_cum[i + 1] = a_cum[i] + A[i]
    ans = 0
    for i in range(len(A)-1):
        ans += A[i] * (a_sum - a_cum[i+1]) % mod
        ans %= mod
    print(ans)

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

d = 10 ** 9 + 7
n = int(input())
lista = [int(x) for x in input().split()]
for k in lista:
    k %= d

total = 0
for i in range(n-1):
    for j in range(i+1, n):
        total += lista[i] * lista[j]
total %= d
print(total)


### FIXED CODE ###

d = 10 ** 9 + 7
n = int(input())
lista = [int(x) for x in input().split()]
for k in lista:
    k %= d

totalJ = sum(lista)

total = 0
for i in range(n-1):
    totalJ -= lista[i]
    total += totalJ * lista[i]
total %= d
print(total)
### BUGGY CODE ###

# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt
from fractions import gcd
from itertools import permutations

def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas



N = intinput()
# S = input()
# A, B, C, D, E, F = mulinputs()
datas = list(mulinputs())
# datas = lineinputs(input)

cnt = 0
for i in range(0,N):
    is_clear = True
    for j in range(0,i):
        if datas[j] < datas[i]:
            is_clear = False
            break
    if is_clear:
        cnt += 1

# 出力
print(cnt)




### FIXED CODE ###

# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt
from fractions import gcd
from itertools import permutations

def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas



N = intinput()
# S = input()
# A, B, C, D, E, F = mulinputs()
datas = list(mulinputs())
# datas = lineinputs(input)

M = 1001000
cnt = 0
l = len(datas)
# for i in range(0,N):
#     is_clear = True
#     for j in range(0,(i+1)>>1):
#         dp0 = datas[2*j] if 2*j < l else M
#         dp1 = datas[2*j+1] if 2*j < l else M
#         if dp0 < datas[i]:
#             is_clear = False
#             break
#         if dp1 < datas[i]:
#             is_clear = False
#             break
#     if is_clear:
#         cnt += 1
dmap = dict()
for i in range(1, len(datas)+1):
    dmap[datas[i-1]] = i
counter = N
for i in range(1, len(datas)+1):
    if dmap[i]-1 > counter:
        continue
    counter -= (counter - (dmap[i]-1))
    cnt +=1
    if counter <=0:
        break


# 出力
print(cnt)
### BUGGY CODE ###

def main():
    S = str(input())
    S += "B"
    N = len(S)
    for i in range(N-1):
        if S[i] == "B" and S[i+1] == "C":
            S = S[:i]+"DE"+S[(i+2):]
    S = S.replace("E","")
    left = 0
    count = 0
    rep = 0
    ar = 0
    N = len(S)
    for i in range(N):
        if S[i] == "D":
            count += 1
            rep += i-left
        elif S[i] == "B" or S[i] == "C":
            ar += rep-(count*(count-1)//2)
            rep = 0
            count = 0
            left = i+1

    print(ar)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    S = input().replace("BC","D")
    ans = count = 0
    for i in S:
        if i == "A":
            count += 1
        elif i == "D":
            ans += count
        else:
            count = 0

    print(ans)

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

import math
A, B, N = map(int, input().split())
ans = 0
for x in range(1, N+1):
	y = math.floor(A * x / B) - A * math.floor(x / B)
	ans = max(ans, y)
print(ans)

### FIXED CODE ###

import math
A, B, N = map(int, input().split())
if N >= B:
	N = B - 1
ans = math.floor(A * N / B)
print(ans)
### BUGGY CODE ###

o=lambda:map(int,raw_input().split())
T,F=True,False
n,k=o()
e=[[] for _ in [0]*n]
exec('a,b=o();e[a-1]+=[b-1];e[b-1]+=[a-1];'*(n-1))
a=10**5
def dfs(x,f):
 if f>=0:l[f]=T
 q=[(x,0)]
 while len(q):
  v,c=q.pop(0)
  if c>k/2:break
  l[v]=T
  for w in e[v]:
   if ~l[w]:q+=[(w,c+1)]
 return n-l.count(T)
if k%2:
 for i in range(n):
  for j in e[i]:
   if i<j:l=[F]*n;dfs(i,j);a=min(a,dfs(j,i))
else:
 for i in range(n):l=[F]*n;a=min(a,dfs(i,-1))
print a


### FIXED CODE ###

ii=lambda:map(int,raw_input().split())
n,k=ii()
T,F=True,False
e=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=ii()
    e[a-1]+=[b-1];e[b-1]+=[a-1]
cost=[0]*n
ans=10**5
def dfs(x,f):
    if f>=0:vis[f]=T
    q=[(x,0)]
    while len(q):
        v,c=q.pop(0)
        if c>k/2:break
        cost[v]=c;vis[v]=T
        for w in e[v]:
            if not vis[w]:q+=[(w,c+1)]
    return n-vis.count(T)
if k%2:
    for i in range(n):
        for j in e[i]:
            if i<j:vis=[F]*n;dfs(i,j);ans=min(ans,dfs(j,i))
else:
    for i in range(n):vis=[F]*n;ans=min(ans,dfs(i,-1))
print ans
### BUGGY CODE ###

N, W = map(int, input().split())
K = [[] for i in range(N)]
for i in range(N):
    K[i] = list(map(int, input().split()))

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(1,N+1):
    w, v = K[i-1]
    for sum_w in range(W+1):
        if sum_w-w>=0:
            dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-w]+v)
        else:
            dp[i][sum_w] = dp[i-1][sum_w]
print(dp[-1][-1])

### FIXED CODE ###

N, W = map(int, input().split())
K = [[] for i in range(N)]
for i in range(N):
    K[i] = list(map(int, input().split()))

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(1,N+1):
    w, v = K[i-1]
    for sum_w in range(W+1):
        if sum_w-w>=0:
            dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-w]+v)
        else:
            dp[i][sum_w] = dp[i-1][sum_w]
print(dp[-1][-1])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

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

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

K = min(K, 50)

for _ in range(K):
    imos = [0] * (N + 1)

    for i in range(N):
        a = A[i]
        s = max(0, i - a)
        e = min(N, i + a + 1)
        imos[s] += 1
        imos[e] -= 1

    nxt = [0] * N
    t = 0
    for i in range(N):
        t += imos[i]
        nxt[i] = t

    A = nxt

print(" ".join(map(str, A)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

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

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

K = min(K, 100)

for _ in range(K):
    imos = [0] * (N + 1)

    for i in range(N):
        a = A[i]
        s = max(0, i - a)
        e = min(N, i + a + 1)
        imos[s] += 1
        imos[e] -= 1

    nxt = [0] * N
    t = 0
    for i in range(N):
        t += imos[i]
        nxt[i] = t

    A = nxt

print(" ".join(map(str, A)))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, A: "List[int]"):
    stack = [-1]

    for i in range(N):
        for j in range(len(stack)):
            if stack[j] < A[i]:
                stack[j] = A[i]
                break
        else:
            stack.append(A[i])
    
    print(len(stack))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
from bisect import bisect_left

def solve(N: int, A: "List[int]"):
    b = deque([A[0]])
    for a in A[1:]:
        if a <= b[0]:
            b.appendleft(a)
        else:
            idx = bisect_left(b, a)
            b[idx-1] = a
    print(len(b))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [float("inf") for _ in range(n)]
dp[0] = 0
for i in range(n-1):
    for j in range(1,k+1):
        if i<n-j:
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]))
print(dp[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [float("inf") for _ in range(n)]
dp[0] = 0
for i in range(n-1):
    for j in range(1,k+1):
        if i<n-j:
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]))
print(dp[n-1])
### BUGGY CODE ###

from sys import stdin,setrecursionlimit
from copy import deepcopy
import heapq

n,m = map(int,stdin.readline().rstrip().split())

li = [[0 for i in range(n+1)]for j in range(n+1)]

inf = 10**10

def all_pairs_shortest_paths(W):
    # 頂点の数
    n = len(W)
    # 結果を格納する行列を用意する
    res = [[0] * n for i in range(n)]
    # 用意した行列を初期化する
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    # 動的計画法ですべての超点間の最短距離を求める
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

lin = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]

true = [True]*(n+1)
point = 0

for j in range(m):
    lis = []
    for num,i in enumerate(lin):
        if num != j:
            lis.append(i)
    liv = [[0 for e in range(n+1)]for o in range(n+1)]
    for kp in lis:
        liv[kp[0]][kp[1]] = 1
        liv[kp[1]][kp[0]] = 1
    kota = all_pairs_shortest_paths(liv)[1:]
    flag = True
    for kk in kota:
        if inf in kk[1:]:
            flag = False
    if flag:
        point += 1

print(m-point)

### FIXED CODE ###

from sys import stdin

inf = 10**3
n,m = [int(x) for x in stdin.readline().rstrip().split()]

li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
nu = []

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    #k：中継
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
point = 0
for i in range(m):
    d = [[inf for i in range(n)]for j in range(n)]
    lin = li[:i]+li[i+1:]
    for j in range(m-1):
        d[lin[j][0]-1][lin[j][1]-1] = 1
        d[lin[j][1]-1][lin[j][0]-1] = 1
    for k in range(n):
        d[k][k] = 0
    lis = warshall_floyd(d)
    for i in lis:
        if inf in i:
            point += 1
            break
print(point)