The winter in Berland lasts n days. For each day we know the forecast for the average air temperature that day. 

Vasya has a new set of winter tires which allows him to drive safely no more than k days at any average air temperature. After k days of using it (regardless of the temperature of these days) the set of winter tires wears down and cannot be used more. It is not necessary that these k days form a continuous segment of days.

Before the first winter day Vasya still uses summer tires. It is possible to drive safely on summer tires any number of days when the average air temperature is non-negative. It is impossible to drive on summer tires at days when the average air temperature is negative. 

Vasya can change summer tires to winter tires and vice versa at the beginning of any day.

Find the minimum number of times Vasya needs to change summer tires to winter tires and vice versa to drive safely during the winter. At the end of the winter the car can be with any set of tires.


-----Input-----

The first line contains two positive integers n and k (1 ≤ n ≤ 2·10^5, 0 ≤ k ≤ n) — the number of winter days and the number of days winter tires can be used. It is allowed to drive on winter tires at any temperature, but no more than k days in total.

The second line contains a sequence of n integers t_1, t_2, ..., t_{n} ( - 20 ≤ t_{i} ≤ 20) — the average air temperature in the i-th winter day. 


-----Output-----

Print the minimum number of times Vasya has to change summer tires to winter tires and vice versa to drive safely during all winter. If it is impossible, print -1.


-----Examples-----
Input
4 3
-5 20 -3 0

Output
2

Input
4 2
-5 20 -3 0

Output
4

Input
10 6
2 -5 1 3 0 0 -4 -3 1 0

Output
3



-----Note-----

In the first example before the first winter day Vasya should change summer tires to winter tires, use it for three days, and then change winter tires to summer tires because he can drive safely with the winter tires for just three days. Thus, the total number of tires' changes equals two. 

In the second example before the first winter day Vasya should change summer tires to winter tires, and then after the first winter day change winter tires to summer tires. After the second day it is necessary to change summer tires to winter tires again, and after the third day it is necessary to change winter tires to summer tires. Thus, the total number of tires' changes equals four.

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python3
def solve():
    n, k = list(map(int, input().split()))
    temps = list(map(int, input().split()))

    summer_seqs = []
    winter_seqs = []

    cur_season = 1
    cur_len = 0
    for t in temps:
        # print("Handling", t)
        if cur_season * t > 0 or (t == 0 and cur_season == 1):
            cur_len += 1
            # print("Adding...")
        else:
            # print("Thats new!")
            if cur_season == 1:
                summer_seqs.append(cur_len)
            else:
                winter_seqs.append(cur_len)
            cur_len = 1
            cur_season = -cur_season
    if cur_season == 1:
        summer_seqs.append(cur_len)
    else:
        winter_seqs.append(cur_len)

    summer_seqs = summer_seqs[1:]

    cur_len = sum(winter_seqs)

    if cur_len > k:
        return -1

    if len(summer_seqs) == 0:
        return 1 if len(winter_seqs) != 0 else 0

    changes = len(summer_seqs) + len(winter_seqs)

    last_sum_seq = None
    if temps[-1] >= 0:
        last_sum_seq = summer_seqs[-1]
        summer_seqs = summer_seqs[:-1]

    summer_seqs = list(sorted(summer_seqs))

    # print("Changes needed so far:", changes)
    # print("Summer seqs: ", len(summer_seqs))
    # print("Last summer seq:", last_sum_seq)
    # print("Can drive for another", k - cur_len)

    for s in summer_seqs:
        if k - cur_len >= s:
            changes -= 2
            cur_len += s
        else:
            break

    # print("Before last summer we can drive for",
    #       k - cur_len, "having ", changes, "changes")

    if last_sum_seq is not None:
        if k - cur_len >= last_sum_seq:
            # print("and dont change at last")
            changes -= 1

    return changes


def __starting_point():
    print(solve())

__starting_point()

def solve(k, s):
    w = [0]
    for c in s:
        if c < 0:
            if w[-1] >= 0:
                w.append(-1)
            else:
                w[-1] -= 1
        else:
            if w[-1] < 0:
                w.append(1)
            else:
                w[-1] += 1
    begin, end = w[0], w[-1]
    if len(w) == 1 and w[0] > 0:
        return 0
    if begin > 0:
        w.pop(0)
    if end > 0:
        w.pop()
    neg_seg = [t for t in w if t < 0]
    pos_seg = [t for t in w if t > 0]
    d = -sum(neg_seg)
    if d > k: return -1
    changes = 2*len(neg_seg) - (end < 0)

    pos_seg.sort()
    for seg in pos_seg:
        d += seg
        if d > k:
            if end > 0 and d-seg+end <= k:
                return changes-1
            else:
                return changes
        else:
            changes -= 2

    if end > 0 and d+end <= k:
        return changes-1
    else:
        return changes
    
    
            
n, k = list(map(int, input().split()))
s = [int(x) for x in input().split()]
print(solve(k, s))


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

f = 0
while f < n and w[f] >= 0:
    f += 1

if f == n:
    print(0)
    return

b = n - 1
while b >= 0 and w[b] >= 0:
    b -= 1

# if n == b - f + 1:
#     print(1)
#     return

if f == b:
    if k == 0:
        print(-1)
        return

    if f+1 == n:
        print(1)
        return
    else:
        if (k - 1) >= (n - (b + 1)):
            print(1)
            return
        else:
            print(2)
            return

inv = []
ps = 0
ns = 0
for i in range(f, b):
    if w[i] >= 0:
        ps += 1
        if w[i+1] < 0:
            inv.append(ps)
    elif w[i] < 0:
        ns += 1
        if w[i+1] >= 0:
            ps = 0
ns += 1
spare = k - ns

if spare < 0:
    print(-1)
    return

if not inv:
    if w[n-1] < 0:
        print(1)
        return
    else:
        if spare >= (n - (b + 1)):
            print(1)
            return
        else:
            print(2)
            return

invs = sorted(inv)

if spare < invs[0]:
    ch = (len(invs) + 1) * 2
    remainder = spare
else:
    use, invsn = invs[0], -1
    for i in range(1, len(invs)):
        use += invs[i]
        if spare < use:
            use -= invs[i]
            invsn = i
            break

    if invsn == -1:
        invsn = len(invs)

    ch = (len(invs) - invsn + 1) * 2
    remainder = spare - use

if remainder >= (n - (b + 1)):
    ch -= 1

print(ch)



#!/usr/bin/env python3
def ri():
    return list(map(int, input().split()))

n, k = ri()

t = list(ri())
tt = []
mc = 0
for i in range(n):
    if i == 0:
        if t[i] < 0:
            tt.append(-1)
            mc += 1
        else:
            tt.append(1)
        continue
    if t[i] < 0:
        mc += 1
        if t[i-1] >= 0:
            tt.append(-1)
        continue
    else:
        if t[i-1] >= 0:
            tt[-1] = tt[-1] + 1
        else:
            tt.append(1)
if mc > k:
    print(-1)
    return
if tt[0] != -1:
    tt = tt[1:]

if len(tt) == 0:
    print(0)
    return

ttt = []
maxs = len(tt)
k2 = k
tt2 = tt[:]

# exclude last tt
if tt[-1] != -1:
    tt = tt[:-1]

for i in tt:
    if i > 0:
        ttt.append(i)
k -= mc
ttt.sort()
for i in ttt:
    if k -i >= 0:
        k -= i
        maxs -= 2
    else:
        break

# include last tt
ttt2 = []
maxs2 = len(tt2)
for i in tt2:
    if i > 0:
        ttt2.append(i)

k2 -= mc
check = 0
ttt2.sort()
for i in ttt2:
    if k2 -i >= 0:
        k2 -= i
        maxs2 -= 2
        if i == tt2[-1] and check == 0:
            maxs2 += 1
            check = 1
    else:
        break

print(min(maxs, maxs2))


import heapq
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.1415926535897932
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
def pscl(num,l=[1]):
    for i in range(num):
        l = map(lambda x,y:x+y,[0]+l,l+[0])
    return l

n,k=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
cnt=[i for i in l if i<0]
m=0
for a,i in enumerate(l):
    if i<0 and m==0:
        m=1
    elif i<0 and l[a-1]>=0:
        m+=1
d={}
q=[]
chk=-1
for i in l:
    if i<0:
        if chk>0:
            if chk in d:
                d[chk]+=1
            else:
                d[chk]=1
                heapq.heappush(q,chk)
        chk=0
    elif chk>=0:
        chk+=1
ans=m*2
k-=len(cnt)
while len(q) and k>=q[0]:
    k-=q[0]
    ans-=2
    d[q[0]]-=1
    if d[q[0]]==0:
        heapq.heappop(q)
if k>=chk and chk>-1:
    ans-=1
print(ans if ans>=0 and k>=0 else -1)

import heapq

n,k=[int(i) for i in input().split()]
l=[int(i) for i in input().split()]
cnt=[i for i in l if i<0]
m=0
for a,i in enumerate(l):
    if i<0 and m==0:
        m=1
    elif i<0 and l[a-1]>=0:
        m+=1
d={}
q=[]
chk=-1
for i in l:
    if i<0:
        if chk>0:
            if chk in d:
                d[chk]+=1
            else:
                d[chk]=1
                heapq.heappush(q,chk)
        chk=0
    elif chk>=0:
        chk+=1
ans=m*2
k-=len(cnt)
while len(q) and k>=q[0]:
    k-=q[0]
    ans-=2
    d[q[0]]-=1
    if d[q[0]]==0:
        heapq.heappop(q)
if k>=chk and chk>-1:
    ans-=1
print(ans if ans>=0 and k>=0 else -1)

n, k = list(map(int, input().split()))
days = list(map(int, input().split()))
a = [0 for i in range(n)] # for < 0
b = [0 for i in range(n)] # for >= 0
asum = 0
ia = 0
ib = 0
inf = n + 199

for x in days:
    if x < 0:
        a[ia] += 1
        asum += 1
        if b[ib] != 0:
            ib += 1
    else:
        b[ib] += 1
        if a[ia] != 0:
            ia += 1
changes = ia + 1 if a[ia] > 0 else ia
changes += changes - 1
if (a[ia] == 0):
    ia -= 1
if b[ib] == 0:
    ib -= 1
if asum > k:
    print(-1)
    quit()
for i in range(ia, n):
    a[i] = inf if a[i] == 0 else a[i]
for i in range(ib, n):
    b[i] = inf if b[i] == 0 else b[i]
if days[0] >= 0:
    b[0] = inf
lastb = -1
removedlastb = False
if days[len(days) - 1] >= 0 :
    changes += 1
    lastb = b[ib]
b.sort()
# print('ia = ' + str(ia))
# print('changes = ' + str(changes))
curb = 0
# take care abount choosing smth in the middle exept for last\
seccurb = curb
secasum = asum
secchanges = changes
secremovedlastb = removedlastb
while (curb <= ib and asum + b[curb] <= k):
    asum += b[curb]
    if not removedlastb:
        if b[curb] == lastb:
            changes -= 1
            removedlastb = True
        else :
            changes -= 2
    else:
        changes -= 2
    curb += 1
while (seccurb <= ib and secasum + b[seccurb] <= k):
    secasum += b[seccurb]
    if not secremovedlastb:
        if b[seccurb] == lastb:
            secasum -= b[seccurb]
            secremovedlastb = True
        else :
            secchanges -= 2
    else:
        secchanges -= 2
    seccurb += 1
print(max(min(changes, secchanges), 0))


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

winter = []
for i, t in enumerate([int(n) for n in input().split()]):
    if (t < 0): winter.append(i)
    
if (len(winter) > k):
    print(-1)
else:
    ans = len(winter)*2
    k -= len(winter)
    for diff in sorted([winter[i] - winter[i-1] - 1 for i in range(1, len(winter))]):        
        if (k >= diff):
            k -= diff
            ans -= 2         
    print(ans - (1 if len(winter) > 0 and k >= n - winter[-1] - 1 else 0))


from collections import deque
import heapq

def main():
    from sys import stdin
    lines = deque(line.strip() for line in stdin.readlines())
    # lines will now contain all of the input's lines in a list
    n, k = [int(x) for x in lines.popleft().split()]
    temps = deque(int(x) for x in lines.popleft().split())
    temps.appendleft(0)
    streaks = []
    count = 0
    ispositive = True
    numnegative = 0
    changes = 0
    while temps:
        temp = temps.popleft()
        positive = temp >= 0
        if positive:
            count += 1
            if not ispositive:
                changes += 1
        else:
            numnegative += 1
            if ispositive:
                streaks.append(count)
                count = 0
                changes += 1
        ispositive = positive
    if numnegative == 0:
        print(0)
        return
    if numnegative > k:
        print(-1)
        return
    if k >= n:
        print(1)
        return
    k -= numnegative
    heap = streaks[1:]
    heapq.heapify(heap)
    heap2 = list(heap)
    if ispositive:
        heapq.heappush(heap2, count)
    changes2 = changes
    k2 = k
    while heap and k >= heap[0]:
        k -= heapq.heappop(heap)
        changes -= 2
    if ispositive and k > count:
        # don't need to change back to summer tires if we end in winter tires
        changes -= 1
    while heap2 and k2 >= heap2[0]:
        k2 -= heapq.heappop(heap2)
        changes2 -= 2
    if ispositive and (not heap2 or heap2[0] > count):
        changes2 += 1
    print(min(changes, changes2))
        
def __starting_point():
    main()

__starting_point()

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


inF = False
bad = 0
last = None
stretches = [0]
for d in [int(x) >= 0 for x in input().split()]:
    last = d
    if d and not inF:
        continue
    else:
        inF = True
        if d:
            stretches[-1] += 1
        else:
            bad += 1
            if stretches[-1] != 0:
                stretches.append(0)

if bad > k:
    print(-1)
elif bad == 0:
    print(0)
elif n == k:
    print(1)
else:
    k -= bad

    num = 1

    if last:
        num -= 1

    if stretches[-1] == 0:
        del stretches[-1]


    num_ = num
    stretches_ = stretches[:-1]
    k_ = k
    # print(num, stretches, k)

    if len(stretches) > 0:
        num += (len(stretches)) * 2
        last = stretches[-1]
        stretches.sort()

        while len(stretches) > 0 and stretches[0] <= k:
            num -= 2
            k -= stretches[0]
            del stretches[0]

        if not last in stretches:
            num += 1
    # print(num_, stretches_, k_)

    if len(stretches_) > 0:
        num_ += (len(stretches_) + 1) * 2
        stretches_.sort()

        while len(stretches_) > 0 and stretches_[0] <= k_:
            num_ -= 2
            k_ -= stretches_[0]
            del stretches_[0]

        print(min(num, num_))
    else:
        print(num)


import sys

def weather(temp):
    return temp >= 0
    
INF = int(1e+6)
n, k = (int(x) for x in input().split())
day_to_temp = [int(x) for x in input().split()]
day_to_weather = [weather(temp) for temp in day_to_temp]

first_warm = -1
mid_warms = []
colds = []
curr_state = 0
curr_len = 0
switches_made = 0

for weather in day_to_weather:
    if curr_state == 0:
        if weather == 1:
            curr_len += 1
        else:
            first_warm = curr_len
            curr_state = 2
            curr_len = 1
            switches_made += 1
    elif curr_state == 1:
        if weather == 1:
            curr_len += 1
        else:
            mid_warms.append(curr_len)
            curr_state = 2
            curr_len = 1
            switches_made += 1
    else:
        if weather == 1:
            colds.append(curr_len)
            curr_state = 1
            curr_len = 1
            switches_made += 1
        else:
            curr_len += 1


if curr_state == 1:
    last_warm = curr_len
elif curr_state == 2:
    colds.append(curr_len)
    last_warm = INF
else:
    print(0)
    return
    
mid_warms = sorted(mid_warms)
cold_days = sum(colds)
free_days = k - cold_days

if free_days < 0:
    print(-1)
    return
elif free_days == 0:
    print(switches_made)
    return
elif len(mid_warms) > 0:
    i = 0
    while i < len(mid_warms) and free_days - mid_warms[i] >= 0:
        switches_made -= 2
        free_days -= mid_warms[i]
        i += 1
        
if free_days - last_warm >= 0:
    switches_made -= 1
    free_days -= last_warm
    
print(switches_made)
    

    


import sys

def weather(temp):
    return temp >= 0
    
INF = int(1e+6)
n, k = (int(x) for x in input().split())
day_to_temp = [int(x) for x in input().split()]
day_to_weather = [weather(temp) for temp in day_to_temp]

first_warm = -1
mid_warms = []
colds = []
curr_state = 0
curr_len = 0
switches_made = 0

for weather in day_to_weather:
    if curr_state == 0:
        if weather == 1:
            curr_len += 1
        else:
            first_warm = curr_len
            curr_state = 2
            curr_len = 1
            switches_made += 1
    elif curr_state == 1:
        if weather == 1:
            curr_len += 1
        else:
            mid_warms.append(curr_len)
            curr_state = 2
            curr_len = 1
            switches_made += 1
    else:
        if weather == 1:
            colds.append(curr_len)
            curr_state = 1
            curr_len = 1
            switches_made += 1
        else:
            curr_len += 1

if curr_state == 1:
    last_warm = curr_len
elif curr_state == 2:
    colds.append(curr_len)
    last_warm = INF
else:
    print(0)
    return
    
mid_warms = sorted(mid_warms)
cold_days = sum(colds)
free_days = k - cold_days

if free_days < 0:
    print(-1)
    return
elif free_days == 0:
    print(switches_made)
    return
elif len(mid_warms) > 0:
    i = 0
    while i < len(mid_warms) and free_days - mid_warms[i] >= 0:
        switches_made -= 2
        free_days -= mid_warms[i]
        i += 1
        
if free_days - last_warm >= 0:
    switches_made -= 1
    free_days -= last_warm
    
print(switches_made)
    

    


import sys
from collections import deque

def weather(temp):
    return temp >= 0
    
INF = int(1e+6)
n, k = (int(x) for x in input().split())
day_to_temp = [int(x) for x in input().split()]
day_to_weather = [weather(temp) for temp in day_to_temp]

first_warm = -1
mid_warms = []
colds = []
curr_state = 0
curr_len = 0
switches_made = 0

for weather in day_to_weather:
    if curr_state == 0:
        if weather == 1:
            curr_len += 1
        else:
            first_warm = curr_len
            curr_state = 2
            curr_len = 1
            switches_made += 1
    elif curr_state == 1:
        if weather == 1:
            curr_len += 1
        else:
            mid_warms.append(curr_len)
            curr_state = 2
            curr_len = 1
            switches_made += 1
    else:
        if weather == 1:
            colds.append(curr_len)
            curr_state = 1
            curr_len = 1
            switches_made += 1
        else:
            curr_len += 1

if curr_state == 1:
    last_warm = curr_len
elif curr_state == 2:
    colds.append(curr_len)
    last_warm = INF
else:
    print(0)
    return
    
mid_warms_deque = deque(sorted(mid_warms, reverse=True))
cold_days_nr = sum(colds)
free_days = k - cold_days_nr

if free_days < 0:
    print(-1)
    return
elif free_days == 0:
    print(switches_made)
    return
elif len(mid_warms) > 0:
    while mid_warms_deque:
        curr_warm_len = mid_warms_deque.pop()
        if free_days - curr_warm_len >= 0:
            switches_made -= 2
            free_days -= curr_warm_len
        
if free_days - last_warm >= 0:
    switches_made -= 1
    free_days -= last_warm
    
print(switches_made)
    

    


import sys
from collections import deque

def weather(temp):
    return temp >= 0
    
INF = int(1e+6)
n, k = (int(x) for x in input().split())
day_to_temp = [int(x) for x in input().split()]
day_to_weather = [weather(temp) for temp in day_to_temp]

first_warm = -1
mid_warms = []
colds = []
curr_state = 0
curr_len = 0
switches_made = 0

for weather in day_to_weather:
    if curr_state == 0:
        if weather == 1:
            curr_len += 1
        else:
            first_warm = curr_len
            curr_state = 2
            curr_len = 1
            switches_made += 1
    elif curr_state == 1:
        if weather == 1:
            curr_len += 1
        else:
            mid_warms.append(curr_len)
            curr_state = 2
            curr_len = 1
            switches_made += 1
    else:
        if weather == 1:
            colds.append(curr_len)
            curr_state = 1
            curr_len = 1
            switches_made += 1
        else:
            curr_len += 1

if curr_state == 1:
    last_warm = curr_len
elif curr_state == 2:
    colds.append(curr_len)
    last_warm = INF
else:
    print(0)
    return
    
mid_warms_deque = deque(sorted(mid_warms, reverse=True))
cold_days_nr = sum(colds)
free_days = k - cold_days_nr

if free_days < 0:
    print(-1)
    return
elif free_days == 0:
    print(switches_made)
    return
elif len(mid_warms) > 0:
    while mid_warms_deque:
        curr_warm_len = mid_warms_deque.pop()
        if not free_days - curr_warm_len >= 0:
            break
        switches_made -= 2
        free_days -= curr_warm_len
        
if free_days - last_warm >= 0:
    switches_made -= 1
    free_days -= last_warm
    
print(switches_made)
    

    


f = lambda: map(int, input().split())
n, k = f()
s, d = [], -1
for q in f():
    if q < 0:
        k -= 1
        if d > 0: s += [d]
        d = 0
    elif d + 1: d += 1
s.sort()
def g(k, d):
    d += len(s) << 1
    for q in s:
        if q > k: break
        k -= q
        d -= 2
    return d
print(0 if d < 0 else -1 if k < 0 else g(k, 2) if k < d else min(g(k, 2), g(k - d, 1)))

f = lambda: map(int, input().split())
n, k = f()
s, d = [], -1
for q in f():
    if q < 0:
        k -= 1
        if d > 0: s += [d]
        d = 0
    elif d > -1: d += 1
s.sort()
t = 2 * len(s)
for q in s:
    if q > k: break
    k -= q
    t -= 2
print(-1 if k < 0 else 0 if d < 0 else 2 + t - (k >= d))

n, k = [int(i) for i in input().split()]
t = [int(i) for i in input().split()]
colddays = [i for i in range(n) if t[i]<0 ]
num_colddays = len(colddays)
if num_colddays == 0:
    print(0)
elif k >= n:
    print(1)
else:
    if num_colddays > k:
        print(-1)
    else:
        k -= num_colddays
        ans = 0
        for i in range(1, len(colddays)):
            if colddays[i] - colddays[i-1] > 1:
                ans += 1
        ans += 1
        ans *= 2
        gap = [0 for i in range(num_colddays)]
        for j in range(1, num_colddays):
            gap[j-1] = colddays[j] - colddays[j-1]-1
        positivegap = [j for j in gap if j > 0]
        positivegap = sorted(positivegap)
        for i in positivegap:
            if k >= i:
                k -= i
                ans -= 2
            else:
                break
        remain = n - 1 - colddays[-1]
        if k >= remain:
            ans -= 1
        print(ans)


_, k = map(int, input().split())
val = [0] + list(map(int, input().split()))
n = len(val)
pls = []

cur, i, sm  = 0, 0, 0
while i < n:
    if val[i] >= 0:
        cur += 1
    else:
        if cur > 0:
            pls.append(cur)
        cur = 0
    i += 1

sm = sum(p for p in pls)
pls = pls[1:]

if cur > 0:
    one = cur
    sm += cur
else:
    one = 10 ** 19

ans = 0

for i in range(1, n):
    if (val[i] >= 0 and val[i - 1] < 0) or (val[i] < 0 and val[i - 1] >= 0):
        ans += 1

if n - sm > k:
    print(-1)
else:
    pls.sort()
    rem = k - (n - sm)
    for p in pls:
        if rem >= p:
            rem -= p
            ans -= 2

    if rem >= one:
        ans -= 1

    print(ans)

n,k=map(int,input().split())
d=list(map(int,input().split()))
p=[]
count=0
count1=0
for i in range(len(d)):
    if d[i]>=0:
        count+=1
    if d[i]<0 or i==len(d)-1:
        p.append(count)
        count=0
        count1+=1
if d[len(d)-1]>=0:
    count1-=1
if count1==0:
    print(0)
    return
a=p.pop() if d[len(d)-1]>=0 else 0
if len(p)>0:
    p.reverse()
    p.pop()
    p.sort()
count=k-len(p)-1 if count1>1 else k-count1
if count<0:
    print(-1)
    return
count1=0
for i in range(len(p)):
    if(count-p[i]>=0):
        count1+=1
        count-=p[i]
    else:
        break
ans=2*(len(p)+1-count1)
if count-a>=0:
    ans-=1
print(ans)

import math
from collections import Counter, defaultdict
from itertools import accumulate

R = lambda: map(int, input().split())
n, k = R()
ts = list(R()) + [-1]
k -= sum(1 if t < 0 else 0 for t in ts[:n])
res = 0 if ts[0] >= 0 else 1
for i in range(1, n):
    if ts[i - 1] < 0 and ts[i] >= 0 or ts[i - 1] >= 0 and ts[i] < 0:
        res += 1
locs = [i for i, t in enumerate(ts) if t < 0]
ps = sorted((y - x - 1, y) for x, y in zip(locs, locs[1:]) if y - x > 1)
res1 = res
k1 = k
for p in ps:
    if k >= p[0]:
        res -= (2 if p[1] < n else 1)
        k -= p[0]
    if k1 >= p[0] and p[1] < n:
        res1 -= 2
        k1 -= p[0]
res = res if k >= 0 else math.inf
res1 = res1 if k1 >= 0 else math.inf
print(min(res, res1) if min(res, res1) < math.inf else -1)

n, k = list(map(int,input().split()))
a = list([int(x)>=0 for x in input().split()])

for ind_positive in range(n):
    if not a[ind_positive]:
        break
else:
    print(0)
    return
a = a[ind_positive:]
n = len(a)

for ind_positive in range(n-1, -1, -1):
    if not a[ind_positive]:
        break
a = a[:ind_positive+1]
len_suf = n-ind_positive-1
n = len(a)
#print(a, len_suf)

b = []
i = 0
while True:
    j = 0
    while i < n and a[i]:
        i += 1
        j += 1
    if j:
        b.append(j)
    i += 1
    if i >= n:
        break
b_sort = b.copy()
b_sort.sort(reverse = True)
s = 0
i = 0
if n-s>k:
    for i in range(len(b)):
        s += b_sort[i]
        if n-s <= k:
            i += 1
            break
if n-s > k:
    ans2 = -1
else:
    ans2 = i*2+2

k -= len_suf
if k < 0:
    ans1 = -1
else:
    b = []
    i = 0
    while True:
        j = 0
        while i < n and a[i]:
            i += 1
            j += 1
        if j:
            b.append(j)
        i += 1
        if i >= n:
            break
    b_sort = b.copy()
    b_sort.sort(reverse = True)
    s = 0
    i = 0
    if n-s>k:
        for i in range(len(b)):
            s += b_sort[i]
            if n-s <= k:
                i += 1
                break
    if n-s > k:
        ans1 = -1
    else:
        ans1 = i*2+1

if ans1 == -1:
    print(ans2)
elif ans2 == -1:
    print(ans1)
else:
    print(min(ans1,ans2))










"""
NTC here
"""
import sys
inp = sys.stdin.readline
 
 
def input(): return inp().strip()
 
 
flush = sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**25)
 
 
def iin(): return int(input())
 
 
def lin(): return list(map(int, input().split()))
 
# range = xrange
# input = raw_input
 
 
def main():
    n, k = lin()
    a = lin()
    a1 = [0]*n
    for i in range(n):
        if a[i]<0:
            a1[i]=1
    sm = sum(a1)
    if sm>k:
        print(-1)
    else:
        sm = k-sm
        lft = []
        ch = 0
        for i in range(n):
            if a1[i]:
                if ch and i-ch:lft.append([ ch, i-ch, 2])
                ch = 0
            else:
                ch+=1
        ext = []
        if ch and i+1-ch:
            ext =[ch, 1+i-ch, 1]
        # print(lft, ext)
        lft.sort()
        a2 = lft + ([ext] if ext else [])
        a2.sort()
        def check(a):
            if not a:return 0
            # print(a)
            s1 = sm
            ans = 0
            for i, j, k in a:
                if s1<i:break
                s1 -= i
                ans+=k
            return ans
        if check(a2)>check(lft):
            lft = a2
        lft = lft[::-1]
        # print(sm, a1)
        # print(lft)
        while sm and lft:
            ch, i, asd = lft.pop()
            if sm<ch:continue
            while sm and ch and i< n:
                a1[i]=1
                i+=1
                sm-=1
                ch-=1
        # print(a1)
        ans = 0
        a1 = [0]+a1
        for i in range(1, n+1):
            if a1[i]!=a1[i-1]:ans+=1
        print(ans)

 
 
 
 
 
 
 

main()
# threading.Thread(target=main).start()