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

n = int(input())
al = list(map(int, input().split()))
q = int(input())
bl = []
cl = []
for i in range(q):
    b,c = map(int, input().split())
    bl.append(b)
    cl.append(c)

shoki = sum(al)
for i in range(q):
    b = bl[i]
    c = cl[i]
    kaisu = al.count(b)
    al = [c if i == b else i for i in al]
    tasu = kaisu * (c - b)
    shoki += tasu
    print(shoki)


### FIXED CODE ###

n = int(input())
al = list(map(int, input().split()))
q = int(input())
bl = []
cl = []
for i in range(q):
    b,c = map(int, input().split())
    bl.append(b)
    cl.append(c)

shoki = sum(al)

dic = {}
for i in al:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1


for i in range(q):
    b = bl[i]
    c = cl[i]
    if b in dic:
        bcount = dic.pop(b)
    else:
        bcount = 0
    if c in dic:
        dic[c] += bcount
    else:
        dic[c] = bcount
    shoki += (c - b)*bcount
    print(shoki)
### BUGGY CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX
for l in range(N):
    l_val = x_dots[l][0]
    for r in range(l+1, N+1):
        for u in range(N):
            u_val = y_dots[u][1]
            for t in range(u+1, N+1):
                xy_dots =  set(x_dots[l:r]) & set(y_dots[u:t])
                if len(xy_dots) >= K:
                    #print("---")
                    #print(l, r, x_dots[l:r])
                    #print(u, t, y_dots[u:t])
                    #print(x_dots[l:r])
                    #l_val = x_dots[l:r][0][0]
                    r_val = x_dots[l:r][-1][0]
                    
                    #u_val = y_dots[u:t][0][1]
                    t_val = y_dots[u:t][-1][1]
                    #print((r-l)*(t-u))
                    if ans > (r_val-l_val)*(t_val-u_val):
                        ans = (r_val-l_val)*(t_val-u_val)
                    else:
                        break
print(ans)


#y_dots = sorted(y_dots, key=lambda x: x[1])
#ans = INT_MAX


### FIXED CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

import numpy as np
import math

n,d,a = map(int,input().split())
xh = [tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
x = np.array(x)
h = np.array(h)

# どこまで巻き込めるかを調査
search = np.searchsorted(x,2*d+x,side="right")-1
count = 0

for i in range(n):
    if h[i] > 0:
        count += math.ceil(h[i]/a)
        h[i:search[i]+1] -= a*math.ceil(h[i]/a)

print(count)

### FIXED CODE ###

from itertools import accumulate
import math
import bisect

n,d,a = map(int,input().split())
xh = [tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
damage = [0]*(n+1)
point = 0

for i in range(n):
    if i != 0:
        damage[i] += damage[i-1]
    bi = bisect.bisect(x,2*d+x[i])
    count = max(math.ceil((h[i]-damage[i])/a),0)
    damage[i] += a*count
    damage[bi] -= a*count
    point += count
    
print(point)
### BUGGY CODE ###

from scipy.special import comb

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

ans=0
for i in range(0,n-1):
    for j in range(i+1,n):
        ans+=A[i]*A[j]
        ans %= 10**9+7
print(ans)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
s=0
ans=0
mod=10**9+7

for i in range(n):
    s+=A[i]

for i in range(0,n-1):
    s-=A[i]
    s%=mod
    ans+=(A[i]*s)
    ans%=mod
print(ans%(10**9+7))
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N, M, S, T, *UVAB = map(int, open(0).read().split())
A, B, R, C = [], [], [], []
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    if a < 1 or b < 1:
        raise ValueError("a < 1 or b < 1")
    A.append(a)
    B.append(b)
    R.append(u)
    C.append(v)

A = dijkstra(csr_matrix((A, (R, C)), (N + 1, N + 1)), False, S)
B = dijkstra(csr_matrix((B, (R, C)), (N + 1, N + 1)), False, T)

C = (A + B).astype(int)

init = 10 ** 15
ans = []
cur = float("inf")
for c in reversed(C[1:]):
    cur = min(cur, c)
    ans.append(init - cur)

for a in reversed(ans):
    print(a)

### FIXED CODE ###

from heapq import heappush, heappop

INF = float("inf")
def dijkstra(E, r):
    D = [INF] * len(E)
    D[r] = 0

    Q = [(0, r)]
    while Q:
        dist, cur = heappop(Q)
        for nxt, cost in E[cur]:
            cand = dist + cost
            if D[nxt] > cand:
                D[nxt] = cand
                heappush(Q, (cand, nxt))

    return D


N, M, S, T, *UVAB = map(int, open(0).read().split())
A = [[] for _ in range(N + 1)]
B = [[] for _ in range(N + 1)]
for u, v, a, b in zip(*[iter(UVAB)] * 4):
    A[u].append((v, a))
    A[v].append((u, a))
    B[u].append((v, b))
    B[v].append((u, b))

A = dijkstra(A, S)
B = dijkstra(B, T)

init = 10 ** 15

ans = []
cur = INF
for a, b in zip(reversed(A[1:]), reversed(B[1:])):
    cur = min(cur, a + b)
    ans.append(init - cur)

for a in reversed(ans):
    print(a)
### BUGGY CODE ###

n,q=map(int,input().split())
par=[-1 for i in range(n+1)]    #par<0なら自身が親で要素の個数、>0なら子で親の位置示す
p=[-1 for i in range(n+1)]
p[1]=0
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    x,y=a,b
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
        x,y=y,x
    par[a]+=par[b]
    par[b]=a
    p[b]=x
    
    return True
ll=[]
for i in range(n-1):
    a=[int(j) for j in input().split()]
    ll.append(a)
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])

l=[0 for i in range(n+1)]
for i in range(q):
    r=[int(j) for j in input().split()]
    l[r[0]]+=r[1]

def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)

#初期化
#par:根なら-size,子なら親の頂点
#wei:親からの距離,根なら0
par = [-1]*(n+1)
wei = [0]*(n+1)

for i in range(n+1):
    unite(p[i],i,l[i])

print(*wei[1:])

### FIXED CODE ###

from collections import deque
n,q=map(int, input().split())
l=[[] for i in range(n+1)]
ans=[0]*(n+1)

for i in range(n-1):
    a,b=[int(j) for j in input().split()]
    l[a].append(b)
    l[b].append(a)
for i in range(q):
    p,x=[int(j) for j in input().split()]
    ans[p]+=x

que=deque()
que.append(1)
ll=[0]*(n+1)
while que:
    y=que.popleft()
    ll[y]=1
    for i in l[y]:
        if ll[i]==1:
            continue
        ans[i]+=ans[y]
        que.append(i)
print(*ans[1:])
### BUGGY CODE ###

H,W,D=map(int,input().split())

dic={}
A=[]
for h in range(H):
    A.append(list(map(int,input().split())))
    for w in range(W):
        dic[A[h][w]]=[h,w]

Q=int(input())

for i in range(Q):
    L,R=map(int,input().split())
    y,x=dic[L]
    ans=0
    while A[y][x]!=R:
        ny,nx=dic[A[y][x]+D]
        ans+=abs(y-ny)+abs(x-nx)
        y=ny
        x=nx
    print(ans)

### FIXED CODE ###

H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    ans=S[R-1]-S[L-1]
    print(ans)
### BUGGY CODE ###

N=int(input())
s=input()
dp=[[0 for _ in range(N+1)] for i in range(N+1)]
MOD=10**9+7
dp[0][N]=1
dp[1]=[1]*N+[0]
for i in range(1,N):
    if s[i-1]=='<':
        for j in range(1,N+1-i):
            for x in range(j):
                dp[i+1][x] =(dp[i+1][x] + dp[i][j])%MOD
    else:
        for j in range(0,N-i):
            for x in range(j,N-i+2):
                dp[i+1][x]=(dp[i+1][x] + dp[i][j])%MOD

print(dp[N][0])


### FIXED CODE ###

N=int(input())
s=input()
dp=[[0 for _ in range(N+1)] for i in range(N+1)]
MOD=10**9+7
dp[0][N]=1
dp[1]=[1]*N+[0]

cum=[0 for _ in range(N+2)]
for i in range(1,N):
    cum[0]=0
    for z in range(1,N-i+2):
        cum[z]=(cum[z-1]+dp[i][z-1])%MOD

    if s[i-1]=='<':
        for j in range(0,N-i):
            dp[i+1][j] =(dp[i+1][j] +cum[N-i+1]-cum[j+1])%MOD
    else:
        for j in range(0,N-i):
            dp[i+1][j]=(dp[i+1][j] + cum[j+1])%MOD

print(dp[N][0])
### BUGGY CODE ###

def input_int_list():
    return [int(thing) for thing in input().split(" ")]


S=list(input())
Q=int(input())
Q_list=[input().split(" ") for i in range(Q)]
for Query in Q_list:
    if Query[0]==str(1):
        S=S[::-1]
    else:
        C=Query[2]
        if Query[1]=="1":
            S=[C]+S
        else:
            S=S+[C]


print("".join(S))

### FIXED CODE ###

from collections import deque


def input_int_list():
    return [int(thing) for thing in input().split(" ")]


S=input()
Q=int(input())
Q_list=[input().split(" ") for i in range(Q)]
hantenness=1
left=[]
right=[]
ans=deque()
ans.extend(list(S))

for Query in Q_list:
    if Query[0]==str(1):
        hantenness*=-1
    else:
        C=Query[2]
        F=int(Query[1])
        if hantenness==1:
            if F==1:
                ans.appendleft(C)
            else:
                ans.append(C)
        else:
            if F==1:
                ans.append(C)
            else:
                ans.appendleft(C)

print("".join(ans) if hantenness==1 else "".join(ans)[::-1])
### BUGGY CODE ###

n,q=map(int, input().split())
S=input()
lr=[list(map(int, input().split())) for _ in range(q)]
for i in range(q):
    l,r=lr[i][0]-1,lr[i][1]-1
    ans=0
    s_parts = S[l:r+1]
    ans=s_parts.count("AC")
    print(ans)

### FIXED CODE ###

n,q=map(int, input().split())
S=input()
lr=[list(map(int, input().split())) for _ in range(q)]
t=[0]*(n+1)
for i in range(n):
    #i桁目までに登場するACを計算する
    t[i+1]=t[i]+(1 if S[i:i+2] == "AC" else 0)
for i in range(q):
    l,r=lr[i][0]-1,lr[i][1]-1
    print(t[r]-t[l])
### BUGGY CODE ###

n, m = map(int, input().split(' '))
l = [set(map(int, input().split(' '))) for _ in range(m)]
max_useless = n*(n-1)//2
ll = [[l[-1]]]

for i in range(2, m+1):
  x = ll[-1]
  ind = []
  se = l[-i]
  for j in range(len(x)):
    if x[j] & se:
      ind.append(j)
  #print(ind)
  if not ind:
    ll.append(ll[-1] + [se])
  else:
    #print(0, ll)
    for j in ind:
      se = se | x[j]
    ll.append([x[j] for j in range(len(x)) if j not in ind] + [se])

def func(lis):
  count = 0
  for x in lis:
    y = len(x)
    count += y*(y-1)//2
  return max_useless - count

#print(ll)
for i in range(2, m+1):
  #print(ll[-i])
  print(func(ll[-i]))
print(max_useless)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
n,m=map(int,input().split())
z=n*(n-1)//2
l=[-1]*n
a=[1]*n
b=[input().split() for _ in range(m)]
c=[0]*m+[z]
def r(s):
  t=l[s]
  if t<0:
    return s
  else:
    l[s]=r(t)
    return l[s]
def f(s):
  return r(int(s)-1)
for i in range(m-1,-1,-1):
  x,y=map(f,b[i])
  if x!=y:
    l[x]=y
    z-=a[x]*a[y]
    a[y]+=a[x]
  c[i]=z
for x in c[1:]:
  print(x)
### BUGGY CODE ###

import numpy as np
from collections import Counter
import collections
a = list(map(int,input().split()))
b = list(map(int,input().split()))
#値を大きさ順に並べる
b = sorted(b)
l = Counter(b)
#dに大きさ順に出てきた数を入れる
d = np.array([])
d = np.append(d,list(l.values()))
c = np.array([])
c = np.append(c,list(l.elements()))
c = list(c)
c =sorted(set(c), key=c.index)
#cに要素を大きさ順にかぶらず入れる
e = [d[i]-c[i] if d[i] - c[i]>=0 else d[i] for i in range(len(c))]
print(int(sum(e)))

### FIXED CODE ###

import numpy as np
from collections import Counter
import collections
a = list(map(int,input().split()))
b = list(map(int,input().split()))
#値を大きさ順に並べる
b = sorted(b)
l = Counter(b)
Num = 0
for k,v in l.items():
  if v-k>=0 :
  	Num += v-k
  else:
    Num += v 
print(Num)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisection(l,r,f,discrete=True,left=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return h if not discrete else l if left else r

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    def check(x): # xが必要かどうかを判定する
        dp=[0]*k # k未満が実現できるかだけを判定
        dp[0]=1
        for i in range(n):
            if(i==x): continue
            newdp=dp[:] # i番目を使わない場合
            a=A[i]
            for j in range(k):
                if(j+a<k):
                    newdp[j+a]=max(dp[j+a],dp[j])
            dp=newdp
        return any(dp[i] for i in range(max(0,k-A[x]),k))
    ans=n
    for i in range(n):
        ans-=check(i)
    print(ans)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A=[min(a,k+1) for a in A]
    A.sort()
    mask=(1<<k)-1

    def check(i): # i のカードを除いて、k-a[i]<=s<k が作れるか
        if(k-A[i]<0): return True
        dp=1
        for j in range(n):
            if(i==j): continue
            dp|=(dp<<A[j])
            dp&=mask

        dp>>=(k-A[i])
        return dp>0

    print(bisection(0,n-1,check,left=False))
resolve()
### BUGGY CODE ###

N, K = map(int, input().split())
H = [int(i) for i in input().split()]
INF = 10 ** 9
dp = [INF] * N
dp[0] = 0

for i in range(1, N):
  dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i - K, 0), i))

print(dp[N - 1])


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

def frog(n, k, h):
    d = [float('inf')] * n
    d[0] = 0

    for i in range(1, n):
        d[i] = min(
            d[j] + abs(h[i] - h[j]) for j in range(max(i - k, 0), i)
        )
    return d[n - 1]


print(frog(n, k, h))
### BUGGY CODE ###

N, Q = [int(i) for i in input().split()]
S = input()
lrs = [[int(i) for i in input().split()] for _ in range(Q)]


for l, r in lrs:
    print(S[l - 1:r].count('AC'))


### FIXED CODE ###

N, Q = [int(i) for i in input().split()]
S = input()
lrs = [[int(i) for i in input().split()] for _ in range(Q)]


cache = {1: {'c': 0, 'm': False}}
cnt = 0
for i in range(1, N):
    if S[i - 1]+S[i] == 'AC':
        cnt += 1
    cache[i + 1] = {'c': cnt, 'm': True}

for l, r in lrs:
    print(cache[r]['c'] - cache[l]['c'])
### BUGGY CODE ###

from sys import setrecursionlimit
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from time import time
import re
setrecursionlimit(10**9)
mod=10**9+7
inf=10**18

n=int(input())
a=[int(x) for x in input().split()]
ans=0
for i in range(n):
    ans+=a[i]*sum(a[i+1:])
    ans%=mod
     
print(ans)

### FIXED CODE ###

from sys import setrecursionlimit
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from time import time
import re
setrecursionlimit(10**9)
mod=10**9+7
inf=10**18

n=int(input())
a=[int(x) for x in input().split()]
cum_a=[]
for i in range(n):
    if i==0:cum_a.append(a[i])
    else:cum_a.append(cum_a[-1]+a[i])
ans=0
for i in range(n-1):
    ans+=a[i]*(cum_a[n-1]-cum_a[i])
    ans%=mod
     
print(ans)
### BUGGY CODE ###

from bisect import bisect_left,bisect_right
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ans=0
for i in range(n):
    for j in range(n):
        if a[i]>=b[j]:
            continue
        else:
            ans+=n-bisect_left(c,b[j]+1)
print(ans)


### FIXED CODE ###

from bisect import bisect_left,bisect_right
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ans=0
for i in range(n):
    A=bisect_left(a,b[i])
    C=n-bisect_right(c,b[i])
    ans+=A*C
print(ans)
### BUGGY CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
ans = 0
for i in A:
    if A.count(i) % 2 != 0:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = set()
for i in range(n):
    k = int(input())
    if k in s:
        s.remove(k)
    else:
        s.add(k)
print(len(s))
### BUGGY CODE ###

import networkx as nx

path = nx.Graph()
room_num, path_num = map(int, input().split())
for i in range(1, room_num):
	path.add_node(i)
for _ in range(path_num):
    a, b = map(int, input().split())
    path.add_edge(a, b)
if nx.is_connected(path):
    print("Yes")
    ans = []
    for n in range(2, room_num+1):
        preans = nx.shortest_path(path, source=n, target=1)
        ans.append(preans[1])
    for n in ans:
      print(n)
else:
    print("No")

### FIXED CODE ###


from collections import deque

room_num, path_num = map(int, input().split(" "))
graph = [[] for _ in range(room_num)]
dis = [-1] * room_num
count = [0] * room_num
count[0] = 1
for _ in range(path_num):
    a, b = map(int, input().split(" "))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
dis[0] = 0
q = deque()
q.append(0)
while q:
    pop = q.popleft()
    for n in graph[pop]:
        if count[n] ==1:
            continue
        else:
            count[n] = 1
            dis[n] = pop+1
            q.append(n)
if sum(dis) == room_num:
    print("No")
else:
    del dis[0]
    print("Yes")
    for s in dis:
        print(s)
### BUGGY CODE ###

import math
# input
stairs, broken = map(int, input().split())
broken_list = []
for i in range(broken):
  broken_list.append(int(input()))
  
# main
goalable = True
for i in range(1, broken):
  if broken_list[i-1] == broken_list[i]-1:
    goalable = False
    break

if goalable:
  broken_list.append(stairs+1)
  now = 0
  ans_list = []
  for b in broken_list:
    cp = b - 1
    stg = cp - now
    tmp = 0
    
    if stg != 0:
      for x in range(stg+1):
        if (stg - x) % 2 == 0:
          y = (stg - x) // 2
          tmp += math.factorial(x+y) // (math.factorial(x) * math.factorial(y))
      ans_list.append(tmp)
    else:
      ans_list.append(1)
    now = b + 1
  
  ans = 1
  for i in ans_list:
    ans = (i * ans) % 1000000007
  print(ans)
else:
  print(0)



### FIXED CODE ###

# input
stairs, broken = map(int, input().split())
conditions = [1] * (stairs + 1)
for i in range(broken):
  tmp = int(input())
  conditions[tmp] = 0
  
# main
for i in range(2, stairs+1):
  conditions[i] *= (conditions[i-1] + conditions[i-2]) % (10**9+7)

print(conditions[stairs])
### BUGGY CODE ###

def draft(A, K, N):
    for _ in range(1, K+1):# 2 * 10**5
        tmp = [0]*(N+1)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        for i in range(N):
            tmp[i+1] += tmp[i]
            A[i] = tmp[i]
    for i in range(N):
        print(A[i], end=" ")

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

if __name__ == "__main__":
    main()

### FIXED CODE ###

def draft(A, K, N):
    for _ in range(1, K+1):# 2 * 10**5
        tmp = [0]*(N+1)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        f = True
        for i in range(N):
            tmp[i+1] += tmp[i]
            A[i] = tmp[i]
            if A[i] != N:
                f = False
        if f:
            break
    for i in range(N):
        print(A[i], end=" ")

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

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

import sys
sys.setrecursionlimit(10 ** 7)

N = input()

# DP
INF = pow(10, 8)
L = len(N)
dp = [[INF] * 2 for _ in range(L+2)]
dp[0][0] = 0

# reverse
N = N[::-1] + '0'


for i in range(L+1):
    for j in range(2):
        # 繰り下がりも加味
        n = int(N[i])
        n += j

        # 更新後のdp
        ni = i + 1

        # 同じだけ払う
        if n < 10:
            dp[ni][0] = min(dp[ni][0], dp[i][j] + n)
        else:
            dp[ni][1] = min(dp[ni][1], dp[i][j])

        # 繰り下がりあり
        if n > 0:
            dp[ni][1] = min(dp[ni][1], dp[i][j] + (10 - n))
        else:
            dp[ni][0] = min(dp[ni][0], dp[i][j])


ans = min(dp[L+1][0], dp[L+1][1])

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N = input()

# DP
INF = pow(10, 8)
L = len(N)
dp = [[INF] * 2 for _ in range(L+2)]
dp[0][0] = 0

# reverse
N = N[::-1] + '0'


for i in range(L+1):
    for j in range(2):
        # 繰り下がりも加味
        n = int(N[i])
        n += j

        # 更新後のdp
        ni = i + 1

        # 10通りから探索
        for a in range(10):
            nj = 0
            b = a - n

            # 繰り下がりあり
            if b < 0:
                b += 10
                nj = 1

            dp[ni][nj] = min(dp[i][j] + a + b, dp[ni][nj])

ans = min(dp[L+1][0], dp[L+1][1])

print(ans)