Problem:
 Max Score: 350 Points   Problem Statement There are N buildings along the line. The i -th building from the left is colored in color i , and its height is currently a_i meters. Chokudai is a mayor of the city, and he loves colorful thigs. And now he wants to see at least K buildings from the left.  You can increase height of buildings, but it costs 1 yens to increase 1 meters. It means you cannot make building that height is not integer. You cannot decrease height of buildings. Calculate the minimum cost of satisfying Chokudai's objective. Note: "Building i can see from the left" means there are no j exists that (height of building j ) ≥ (height of building i ) and j < i .       Input Format   N  K  a_1  a_2  a_3 ... a_N       Output Format Print the minimum cost in one line. In the end put a line break.    Constraints   1 ≤ K ≤ N ≤ 15  1 ≤ a_i ≤ 10^9     Scoring Subtask 1 [ 120 points]   N = K  Subtask 2 [ 90 points]   N ≤ 5  a_i ≤ 7  Subtask 3 [ 140 points]   There are no additional constraints.        Sample Input 1  5 5
3949 3774 3598 3469 3424    Sample Output 1  1541 The optimal solution is (height of buildings from the left) = [3949, 3950, 3951, 3952, 3953] .      Sample Input 2  5 3
7 4 2 6 4    Sample Output 2  7 The optimal solution is (height of buildings from the left) = [7, 8, 2, 9, 4] .

Solution (Python):
import sys
input = sys.stdin.readline
input = sys.stdin.buffer.readline


def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))




import numpy as np
from itertools import combinations

def main():
	n,k=MI()
	ans=10**18

	A=LI()
	A=[A[0]-1]+A
	A=np.array(A)

	for t in combinations(range(n),k):
		B=A.copy()
		tmp=0
		for i in t:
			i+=1
			B[i]=max(B[:i].max()+1,A[i])
			tmp+=B[i]-A[i]
		ans=min(ans,tmp)
	print(ans)

if __name__ == "__main__":
	main()

Solution (Python):


class BitSeacher:
    def __init__(self,bitcount):
        self.counter =0
        self.bitcount = bitcount
        self.mx = 2**bitcount-1
    
    def __next__(self):
        if self.counter > self.mx:
            raise StopIteration()
        ans =[]
        flg =1
        for i in range(self.bitcount):
            if flg & self.counter != 0:
                ans.append(i)
            flg = flg.__lshift__(1)
        self.counter+=1
        return ans

    def __iter__(self):
        return self

def checker(A,group,K):
    if len(group) < K:
        return 10**20

    tbl = [False for i in A]
    for i in group:
        tbl[i]=True
    mx = 0
    count = 0
    for i in range(len(A)):
        if not tbl[i]:
            mx = max(mx,A[i])
            continue
        
        if mx < A[i]:
            mx = A[i]
        else:
            count += mx - A[i] +1
            mx +=1
    return count






def resolve():
    N,K = map(int,input().split())
    A= list(map(int,input().split()))
    mn = 10**20
    for group in BitSeacher(N):
        group.sort()
        mn = min(mn,checker(A,group,K))

    print(mn)



if __name__ == "__main__":
    resolve()

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

min_cost = 1 << 50
for mask in range(1<<N):
    if bin(mask).count('1') < K:
        continue

    cost = 0
    prev_height = 0
    for i in range(N):
        
        if mask & (1<<i) == 0:
            prev_height = max(prev_height, A[i])
            continue

        
        if A[i] <= prev_height:
            cost += prev_height - A[i] + 1
            prev_height += 1
        else:
            prev_height = A[i]
    min_cost = min(min_cost, cost)

print(min_cost)

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))

ans = 10 ** 11
for b in range(1 << n):
    if bin(b).count("1") != k:
        continue

    max_ai = 0
    cost = 0
    for i in range(n):
        if (b & 1 << i):
            if A[i] > max_ai:
                max_ai = A[i]
            else:
                cost += (max_ai + 1) - A[i]
                max_ai += 1
        else:
            max_ai = max(max_ai, A[i])

    ans = min(ans, cost)

print(ans)

Solution (Python):
from sys import stdin
from itertools import combinations
N,K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
ans = 10**18
for i in combinations(range(1,N),K-1):
    tallest = A[0]
    tmp = 0
    for j in range(1,N):
        if j in i:
            if tallest >= A[j]:
                tmp += (tallest - A[j] + 1)
                tallest = (tallest + 1)
            else:
                tallest = max(tallest,A[j])
        else:
            tallest = max(tallest,A[j])
    ans = min(ans,tmp)
print(ans)

Solution (Python):





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

    ans = 10**30
    for i in range(1<<N):
        hght = A[0]
        cst = 0
        cnt = 1
        for j in range(1,N):
            if (i>>j)&1:
                cnt += 1
                if A[j]<=hght: 
                    cst += hght-A[j]+1
                    hght += 1
                else:
                    hght = A[j]
            hght = max(hght,A[j])
        if cnt >= K:
            ans = min(ans,cst)
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    result = float('inf')
    for bit in range(1 << N):
        use = []
        for i in range(N):
            if bit & (1 << i):
                use.append(i)
        if len(use) != K:
            continue

        cost = 0
        eye_height = A[0]

        for i in range(1, N):
            a = A[i]
            if a > eye_height:
                eye_height = a
                continue
            elif i in use:
                eye_height = eye_height + 1
                cost += eye_height - a

        
        
        

        result = min(result, cost)

    print(result)

Solution (Python):
N, K, *A = map(int, open(0).read().split())

ans = 10 ** 9 * 20
for bit in range(2 ** N):
    if bin(bit).count("1") < K or not (bit >> 0 & 1):
        continue

    res = 0
    tmp = A[0]
    for i in range(1, N):
        if bit >> i & 1:
            res += max(0, tmp - A[i] + 1)
            tmp = max(A[i], tmp + 1)
        else:
            tmp = max(A[i], tmp)
    ans = min(ans, res)

print(ans)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 10**11


for i in range(2**(n-1)):
  select = [0]
  len_select = 1
  for j in range(n-1):
    if i >> j & 1 and len_select < k:
      select.append(j+1)
      len_select += 1
  
  
  ok = 1
  
  for m in select:
    for l in range(n):
      if l in select: continue
      if l < m and a[l] >= a[m]:
        
        ok = 0
  if ok == 0 or len_select < k: continue
  else:
    ans_i = 0
    pre_val = a[0]
    for j in range(1,k):
      
      if pre_val >= a[select[j]]:
        ans_i += pre_val+1 - a[select[j]]
        pre_val += 1
      else:
        pre_val = a[select[j]]
  ans = min(ans,ans_i)
print(ans)

Solution (Python):
N,K=map(int, input().split())
*A,=map(int, input().split())

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x = x + (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

ans = 10**18

for p in range(1<<N):
    P=p
    if popcount(p) < K: continue
    cost = 0
    mx = 0
    for a in A:
        flag = p&1
        p >>= 1
        if flag:
            if mx >= a:
                cost += mx + 1 - a
                mx += 1
            else: mx = a
        else: mx = max(mx, a)
    ans = min(ans, cost)

print(ans)

Solution (Python):
from itertools import product
N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 10 ** 18
for build in product(range(2), repeat=N - 1):
    if sum(build) != K - 1:
        continue

    
    cost = 0
    h = A[0]
    for i, p in enumerate(build, start=1):
        if p == 0:
            h = max(h, A[i])
            continue
        if A[i] > h:
            h = A[i]
            continue
        else:
            h += 1
            cost += (h - A[i])
    ans = min(ans, cost)

print(ans)

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
if K==1:
    print(0)
    exit()

ans = 10**12
for b in range(1<<(N-1)):
    h = A[0]
    k = 1
    cost = 0
    for i in range(N-1):
        a = A[i+1]
        if a > h:
            k += 1
            h = a
        elif b&(1<<i):
            k += 1
            cost += h+1 - a
            h += 1
    if k >= K:
        ans = min(ans, cost)
print(ans)

Solution (Python):
def examA():
    N, L = LI()
    V, D = LI()
    X = [LI()for _ in range(N)]

    ans = 0
    print(ans)
    return

def examB():
    N, K = LI()
    H = 11; W = 7
    S = [[0]*(W+1) for _ in range(H+3)]
    for h in range(H+2):
        for w in range(W):
            S[h+1][w+1] = (S[h][w+1] + S[h+1][w] - S[h][w] + (7*h+w+1))
    
    base = 0
    for h in range(H):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                base += 1
                
    ans = base * ((N-2)//11)
    
    rest = (N-2)%11
    for h in range(rest):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                ans += 1
                
    print(ans)
    return

def examC():
    N, K = LI()
    A = LI()
    loop = 2**N
    ans = inf
    for i in range(loop):
        cnt = 0
        need = 0
        highest = 0
        for j in range(N):
            if i&(1<<j)==0:
                if highest<A[j]:
                    need = inf
                    break
                continue
            cnt += 1
            if highest>=A[j]:
                need += (highest+1-A[j])
                highest = highest + 1
            else:
                highest = A[j]
        if cnt>=K and need<ans:
            ans = need
        
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examC()

"""

"""

Solution (Python):

import itertools

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

mn = 1e12

for v in itertools.product([0,1], repeat=N-1):
    h = A[0]
    p = 0
    if sum(v) < K - 1:
        continue
    for i, vv in enumerate(v):
        if vv == 1:
            p += max(h - A[i+1] + 1, 0)
            h = max(A[i+1], h + 1)
        else:
            h = max(A[i+1], h)
    mn = min(mn, p)

print(mn)

Solution (Python):
n,k = map(int,input().split())
a = list(map(int,input().split()))

ans = 1145141919810364364334
for i in range(1,2**n):
    ls = [0] * n
    qq = []
    
    for j in range(n):
        if (i >> j) & 1:
            ls[j] = 1
            qq.append(j)
            
    if sum(ls) < k:
        continue
        
    else:
        mt = a[0]
        cost = 0
        for j in range(1,n) :
            if mt < a[j]:
                mt = a[j]
            else:
                if ls[j] == 1:
                    cost += mt + 1 - a[j]
                    mt += 1
    ans = min(ans,cost)
    
print(ans)

Solution (Python):
def inpl():
    return list(map(int, input().split()))


def count(i):
    cost, k = 0, 1
    h = A[0]
    for j in range(1, N):
        if A[j] > h:
            k += 1
            h = A[j]
        elif (i >> j) & 1:
            k += 1
            cost += max(h - A[j] + 1, 0)
            h += 1
    return cost, k


N, K = inpl()
A = inpl()

ans = float('inf')
for i in range(1 << N):
    cost, k = count(i)
    if k >= K:
        ans = min(ans, cost)

print(ans)

Solution (Python):
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    ans = 1 << 60
    for bit in range(1 << N):
        bills = A[:]
        
        if bin(bit).count("1") != K:
            continue
        sum_H = 0
        cmb = []  
        for i in range(N):
            if bit >> i & 1:
                cmb.append(i)
        for b in cmb:
            if b == 0:
                continue
            m = max(bills[:b])
            if m < bills[b]: 
                pass
            else:
                sum_H += m + 1 - bills[b] 
                bills[b] = m + 1 
        ans = min(ans, sum_H)

    return print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
import itertools
N, K = list(map(int, input().split()))
A_orig = list(map(int, input().split()))

res = len(A_orig) * max(A_orig)
for pattern in itertools.combinations(range(N), K):
    cnt = 0
    A = A_orig[:]
    for p in pattern:
        if p == 0:
            continue
        extension = max(0, max(A[:p]) - A[p] + 1)
        A[p] += extension
        cnt += extension
    res = min(res, cnt)
    
print(res)

Solution (Python):
N,K = map(int,input().split())
A = [int(i) for i in input().split()]


ans=1000000000*N
for i in range(1<<N):
    bitlist=[]
    for j in range(N):
        bitlist.append((i >> j) & 1)
    if sum(bitlist) < K:
        continue

    tmp_max=0
    nedan=0
    for j in range(N):
        if bitlist[j]==1:
            if tmp_max >= A[j]:
                nedan+=(tmp_max-A[j]+1)
                tmp_max=tmp_max+1
            elif tmp_max < A[j]:
                tmp_max=A[j]
        elif bitlist[j]==0:
            if tmp_max < A[j]:
                tmp_max=A[j]
    ans=min(ans,nedan)
print(ans)

Solution (Python):
def bitcount(x):
  x = x - ((x >> 1) & 0x5555555555555555)
  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
  x = x + (x >> 8)
  x = x + (x >> 16)
  x = x + (x >> 32)
  return x & 0x0000007f
N, K = map(int, input().split())
A = list(map(int, input().split()))
r = float('INF')
for i in range(1<<N):
  if bitcount(i) != K:
    continue
  cost, hights, idx = 0, [], 0
  for j in range(N):
    if j > 0 and i>>j & 1:
      c = max(0, max(hights[idx:j]) - A[j] + 1)
      cost += c
      hights.append(A[j] + c)
      idx = j
    else:
      hights.append(A[j])
  
  r = min(r, cost)
print(r)

Solution (Python):
import itertools

n, k = [int(i) for i in input().split()]
top, *a = [int(i) for i in input().split()]

ans = float("inf")
for pp in itertools.product((0, 1), repeat=n-1):
    now = top
    v = 1
    cost = 0
    for i, p in enumerate(pp):
        if p == 0:
            if a[i] > now:
                now = a[i]
                v += 1
            continue
        now = max(now+1, a[i])
        cost += max(now-a[i], 0)
        v += 1
    if v >= k:
        ans = min(ans, cost)
print(ans)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  
nl = lambda: list(map(int, stdin.readline().split()))

n, K = na()
a = na()
ans = float('inf')
for i in range(2**(n-1)):
    colors = 1
    cost = 0
    tmp = a[0]
    for k in range(n-1):
        if tmp < a[k+1]:
            colors += 1
            tmp = a[k+1]
            continue
        if (i >> k) & 1:
            cost += tmp - a[k+1] + 1
            colors += 1
            tmp += 1
    if colors >= K:
        ans = min(ans, cost)
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    ans=INF
    for i in range(2**N):
        c=0
        tmp=0
        l=a[0]
        for j in range(N):
            if j==0:
                if (i>>j)&1:
                    c+=1
                else:
                    break
            else:
                if (i>>j)&1:
                    c+=1
                    tmp+=max(0,l+1-a[j])
                    l=max(l+1,a[j])
                else:
                    l=max(l,a[j])
        if c>=K:
            ans=min(ans,tmp)
    print(ans)
    

if __name__ == '__main__':
    main()

Solution (Python):
n, k = map(int, input().split())
array = list(map(int, input().split()))
if k == 1:
  print(0)
  quit()
  
import itertools
cost = float('inf')
for cand in itertools.combinations(range(1, n), k-1):
  dp = array[:]
  curr_cost = 0
  for index in cand:
    max_val = max(dp[:index])
    if array[index] > max_val:
      continue
    curr_cost += max_val - array[index] + 1
    dp[index] = max_val + 1
  cost = min(cost, curr_cost)
  
print(cost)

Solution (Python):
n, k = map(int, input().split())

H = list(map(int, input().split()))

min_money = 10**18
for i in range(2**n):
    builds = []
    num_builds = 0
    for j in range(n):
        if ((i>>j)&1):
            builds += [j]
            num_builds += 1
    
    if num_builds==k:
        current_h = 0
        money = 0
        for b in builds:
            if b>0:
                current_h = max(max(H[:b]), current_h)
            if H[b]>current_h:
                current_h = H[b]
            elif H[b]<=current_h:
                d_h = current_h - H[b] + 1
                current_h += 1
                money += d_h
            
        if money<min_money:
            min_money = money
            
print(min_money)

Solution (Python):
n,k= map(int, input().split())
a=list(map(int, input().split()))
b=[0]*n
y=a[0]

for i in range(n):
    y=max(y,a[i])
    b[i]=y

ans=pow(10,12)
for i in range(2**(n-1)):
    H=[]
    for j in range(1,n):
        if (i>>(j-1))&1:
            H.append(j)

    if len(H)==k-1:
        cnt = 0
        x = b[0]+1
        for l in range(len(H)):
            if x>=b[H[l]]:
                cnt+=x-a[H[l]]
                x+=1
            else:
                if b[H[l]]==a[H[l]]:
                    x=b[H[l]]+1
                else:
                    cnt+=x-a[H[l]]
                    x=b[H[l]]+1

        ans=min(cnt,ans)

if k==1:
    print(0)
else:
    print(ans)

Solution (Python):


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



costs = []
if N == K:
    cost = 0
    max_height = l_height[0]
    for i in range(1, N):
        if max_height >= l_height[i]:
            cost += (max_height + 1) - l_height[i]
            l_height[i] = max_height + 1
        max_height = l_height[i]
    costs.append(cost)
else:
    for bits in range(2 ** N):
        buildings = []
        
        for i in range(N):
            if bits & (1 << i):
                buildings.append(i)

        l_height_copy = l_height[:]
        cost = 0
        
        if len(buildings) == K:
            
            
            max_height = l_height_copy[0]
            for i in range(1, N):
                if i in buildings:
                    
                    
                    
                    
                    
                    
                    if max_height >= l_height_copy[i]:
                        
                        
                        cost += (max_height + 1) - l_height_copy[i]
                        
                        l_height_copy[i] = max_height + 1
                        max_height = l_height_copy[i]
                        
                    else:
                        max_height = l_height_copy[i]
                else:
                    if l_height_copy[i] > max_height:
                        
                        max_height = l_height_copy[i]
            costs.append(cost)


print(min(costs))

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,k = mi()

a = li()
min_cost = float('inf')

for i in range(2**n):
    select = []
    a2 = a.copy()
    for j in range(n):
        if (i >> j)&1:
            select.append(j)

    if(len(select) != k):
        continue

    cost = 0
    b_max = a2[0]
    for j in range(1,n):
        if j in select:
            if(a2[j] <= b_max):
                cost += b_max+1 - a2[j]
                a2[j] = b_max+1
        b_max = max(b_max, a2[j])
    min_cost = min(min_cost, cost)

print(min_cost)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,k = mi()

a = li()
min_cost = 10**9 * 16

for i in range(2**n):
    select = []
    a2 = a.copy()
    for j in range(n):
        if (i >> j)&1:
            select.append(j)

    if(len(select) != k):
        continue

    cost = 0
    b_max = a2[0]
    for j in range(1,n):
        if j in select:
            if(a2[j] <= b_max):
                cost += b_max+1 - a2[j]
                a2[j] = b_max+1
        b_max = max(b_max, a2[j])
    min_cost = min(min_cost, cost)

print(min_cost)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    ans = float("inf")
    for b in range(1<<(n-1)):
        b <<= 1
        if bin(b).count("1") != k-1:
            continue
        m = a[0]
        s = 0
        for i in range(1,n):
            if not b&(1<<i):
                if m < a[i]:
                    m = a[i]
            else:
                if a[i] <= m:
                    m += 1
                    s += m-a[i]
                else:
                    m = a[i]
        if s < ans:
            ans = s
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    a = LI()
    ans = float("inf")
    for b in range(1<<n):
        if bin(b).count("1") < k:
            continue
        m = 0
        s = 0
        for i in range(n):
            if not b&(1<<i):
                if m < a[i]:
                    m = a[i]
            else:
                if a[i] <= m:
                    m += 1
                    s += m-a[i]
                else:
                    m = a[i]
        if s < ans:
            ans = s
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
def dfs(index):
    global ans
    if index == N:
        if blst.count(1) >= K - 1:
            tmp = a[0]
            anstmp = 0
            for i in range(1, N):
                if blst[i - 1] == 0:
                    if tmp < a[i]:
                        tmp = a[i]
                    continue
                if tmp >= a[i]:
                    anstmp += tmp - a[i] + 1
                    tmp += 1
                else:
                    tmp = a[i]
            ans = min(ans, anstmp)
        return
    for i in range(2):
        blst[index - 1] = i
        dfs(index + 1)
    return

N, K = map(int, input().split())
a = list(map(int, input().split()))
blst = [0] * (N - 1)
ans = float('inf')
dfs(1)

print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import functools 
import sys
import bisect
import string
import math
import time
import random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

N=10**6+2
m=[0]*(N)

n,k=LI()
a=LI()
N=1<<n
ans=inf
for i in range(N):
    c=0
    t=[]
    for j in range(n):
        if (i>>j)&1:
            c+=1
            t+=[j]
    if c!=k:
        continue
    
    alt=0
    ti=0
    M=-1
    for j in range(n):
        
        if j==t[ti]:
            alt+=max(0,M+1-a[j])
            M=max(a[j],M+1)
            ti+=1
        
        if ti==k:
            break
        M=max(M,a[j])
        
    
    if alt<ans:
        ans=alt
print(ans)

Solution (Python):
n, k = map(int, input().split())
pbls = list(map(int, input().split()))
ans = 1e18
for i in range(pow(2, n)):
    bls = pbls[::]
    if (bin(i).count("1") != k):
        continue
    temp = 0
    l = []
    for b in range(n):
        if (i & (1 << b)):
            l.append(b)
    for c in l:
        if (c == 0):
            continue
        else:
            m = max(bls[:c])
            if (m < bls[c]):
                pass
            else:
                temp += m + 1 - bls[c]
                bls[c] = m + 1
    ans = min(ans,temp)
print(ans)

Solution (Python):
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
ans = float('inf')

for i in range(2**N):
    cnt = 0
    last = 0
    cost = 0
    for j in range(N):
        if(A[j] > last):
            cnt += 1
            last = A[j]
        elif(i>>j & 1):
            cnt += 1
            cost += last-A[j]+1
            last += 1
    if(cnt>=K):
        ans = min(ans, cost)
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=10**18
for i in range(2**n):
  build=set()
  maxi=a[0]
  for j in range(n):
    if (i>>j)&1:
      build.add(j)
  cnt=len(build)
  if 0 not in build:
    cnt+=1
  s=0
  for j in range(n):
    if j==0:
      continue
    elif j in build:
      if a[j]<=maxi:
        s+=maxi-a[j]+1
        maxi+=1
      else:
        maxi=a[j]
    else:
      if a[j]>maxi:
        cnt+=1
        maxi=a[j]
  if cnt>=k:
    ans=min(ans,s)
print(ans)

Solution (Python):


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


most_left = buildings[0]
buildings = buildings[1:]
ans = float('inf')
for i in range(2 ** len(buildings)):
    if bin(i).count('1') < k - 1:
        continue
    t = most_left 
    cost = 0
    for j in range(len(buildings)):
        if (i >> j) & 1:
            if t >= buildings[j]:
                cost += t - buildings[j] + 1 
                t += 1 
            else:
                
                t = buildings[j]
        else: 
              
            if t < buildings[j]:
                t = buildings[j]
    ans = min(ans, cost)
print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = float('inf')
for i in range(2 ** (N-1)):
    l = [0] * (N-1)
    for j in range(N-1):
        if (i >> j) & 1:
            l[j] = 1
    cost = 0
    AA = A.copy()
    for k in range(N-1):
        if l[k] == 1:
            maxA = max(AA[:k+1])
            if maxA >= AA[k+1]:
                diff = maxA - AA[k+1] + 1
                AA[k+1] = maxA + 1
                cost += diff
    cnt = 1
    for num in range(1, N):
        if AA[num] > max(AA[:num]):
            cnt += 1
    if cnt >= K:
        ans = min(ans, cost)
print(ans)

Solution (Python):

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

ans=10**15
for i in range(2**n):
    if bin(i).count('1')<k:
        continue
    max_tmp=0
    res=0
    for j in range(n):
        if (i>>j)&1:
            if a[j]>max_tmp:
                max_tmp=a[j]
            else:
                res+=max_tmp-a[j]+1
                max_tmp+=1
        else:
            max_tmp=max(max_tmp,a[j])
    ans=min(res,ans)
print(ans)

Solution (Python):
n, k = map(int, input().split())

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

ans = float('inf')
for i in range(1 << n):
    res = 0
    cnt = 0
    m = 0
    for j in range(n):
        if i >> j & 1:
            cnt += 1
            res += max(m-a[j] + 1, 0)
            m = max(m+1, a[j])
        else:
            m = max(m, a[j])

    if cnt >= k:
        ans = min(ans, res)

print(ans)

Solution (Python):
from itertools import combinations

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

b = list(range(1, n))
c = combinations(b, k-1)

min_sum = 10**30
for i in c:
    sum = 0
    target = a[0] + 1
    for j in range(1, n):
        if j in i:
            if target >= a[j]:
                sum += (target - a[j])
                target += 1
            else:
                target = a[j] + 1
        elif j not in i and a[j] > target:
            target = a[j] + 1
    if sum < min_sum:
        min_sum = sum

print(min_sum)