Given an array A[] of size N and a positive integer K, find the first negative integer for each and every window(contiguous subarray) of size K.
 
Example 1:
Input : 
N = 5
A[] = {-8, 2, 3, -6, 10}
K = 2
Output : 
-8 0 -6 -6
Explanation :
First negative integer for each window of size k
{-8, 2} = -8
{2, 3} = 0 (does not contain a negative integer)
{3, -6} = -6
{-6, 10} = -6
 
Example 2:
Input : 
N = 8
A[] = {12, -1, -7, 8, -15, 30, 16, 28}
K = 3
Output :
-1 -1 -7 -15 -15 0 
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function printFirstNegativeInteger() which takes the array A[], its size N and an integer K as inputs and returns the first negative number in every window of size K starting from the first till the end. If a window does not contain a negative integer , then return 0 for that window.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(K)
Constraints:
1 <= N <= 10^{5}
-10^{5} <= A[i] <= 10^{5}
1 <= K <= N

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3



def printFirstNegativeInteger( A, N, K):

    # code here

Solutions:
from collections import deque

def printFirstNegativeInteger(A, N, K):
	result = []
	window_negatives = deque()
	for i in range(K):
		if A[i] < 0:
			window_negatives.append(i)
	if window_negatives:
		result.append(A[window_negatives[0]])
	else:
		result.append(0)
	for i in range(K, N):
		while window_negatives and window_negatives[0] <= i - K:
			window_negatives.popleft()
		if A[i] < 0:
			window_negatives.append(i)
		if window_negatives:
			result.append(A[window_negatives[0]])
		else:
			result.append(0)
	return result


def printFirstNegativeInteger(A, N, K):
	i = 0
	j = 0
	res = []
	temp_lis = []
	while j < N:
		if A[j] < 0:
			temp_lis.append(A[j])
		if j - i + 1 < K:
			j += 1
		elif j - i + 1 == K:
			if len(temp_lis) == 0:
				res.append(0)
			else:
				res.append(temp_lis[0])
			if len(temp_lis) != 0 and temp_lis[0] == A[i]:
				temp_lis.pop(0)
			i += 1
			j += 1
	return res


def printFirstNegativeInteger(A, N, K):
	i = 0
	j = 0
	return_vector = []
	neg_list = []
	while j < N:
		if A[j] < 0:
			neg_list.append(A[j])
		if j - i + 1 != K:
			j += 1
		else:
			if len(neg_list) == 0:
				return_vector.append(0)
			else:
				return_vector.append(neg_list[0])
				if A[i] < 0:
					neg_list.pop(0)
			i += 1
			j += 1
	return return_vector


def printFirstNegativeInteger(A, N, K):
	(q, l, h, res) = ([], 0, K - 1, [])
	for i in range(K):
		if A[i] < 0:
			q.append(A[i])
	while h < N:
		if q:
			res.append(q[0])
		else:
			res.append(0)
		if A[l] < 0:
			q.pop(0)
		l += 1
		if h == N - 1:
			break
		h += 1
		if A[h] < 0:
			q.append(A[h])
	return res


from collections import deque

def printFirstNegativeInteger(A, N, K):
	q = deque()
	for i in range(K):
		if A[i] < 0:
			q.append(A[i])
	i = 0
	j = K - 1
	while j < N:
		if len(q) == 0:
			A[i] = 0
		else:
			temp = q[0]
			if A[i] == q[0]:
				q.popleft()
			A[i] = temp
		i += 1
		j += 1
		if j < N and A[j] < 0:
			q.append(A[j])
	for i in range(K - 1):
		A.pop()
	return A


def printFirstNegativeInteger(arr, n, k):
	temp = []
	res = []
	(i, j) = (0, 0)
	while j < n:
		if arr[j] < 0:
			temp.append(arr[j])
		if j - i + 1 < k:
			j += 1
		elif j - i + 1 == k:
			if len(temp) > 0:
				res.append(temp[0])
				if temp[0] == arr[i]:
					temp.pop(0)
			else:
				res.append(0)
			i += 1
			j += 1
	return res


def printFirstNegativeInteger(A, N, K):
	i = 0
	j = 0
	l = []
	ans = []
	while j < N:
		if A[j] < 0:
			l.append(A[j])
		if j - i + 1 < K:
			j += 1
		elif j - i + 1 == K:
			if len(l) == 0:
				ans.append(0)
			else:
				ans.append(l[0])
				if A[i] == l[0]:
					l.pop(0)
			i += 1
			j += 1
	return ans


def printFirstNegativeInteger(arr, n, k):
	start = 0
	end = 0
	neg_nums = []
	res = []
	while end < n:
		if arr[end] < 0:
			neg_nums.append(arr[end])
		if end - start + 1 < k:
			end += 1
		elif end - start + 1 == k:
			if len(neg_nums) > 0:
				res.append(neg_nums[0])
				if arr[start] == neg_nums[0]:
					neg_nums.pop(0)
			else:
				res.append(0)
			start += 1
			end += 1
	return res


from collections import deque

def printFirstNegativeInteger(A, N, K):
	queue = deque()
	ans = []
	isFirst = True
	for i in range(K):
		if A[i] < 0:
			if isFirst:
				ans.append(A[i])
				isFirst = False
			queue.append(i)
	if len(queue) == 0:
		ans.append(0)
	for i in range(1, N - K + 1):
		if A[i + K - 1] < 0:
			queue.append(i + K - 1)
		while len(queue) > 0 and queue[0] < i:
			queue.popleft()
		if len(queue) == 0:
			ans.append(0)
		else:
			ans.append(A[queue[0]])
	return ans


from collections import deque

def printFirstNegativeInteger(a, n, k):
	q = deque()
	(i, j) = (0, 0)
	ans = []
	while j < n:
		if a[j] < 0:
			q.appendleft(a[j])
		if j - i + 1 < k:
			j += 1
		elif j - i + 1 == k:
			if len(q) != 0:
				if q[-1] == a[i]:
					ans.append(q.pop())
				else:
					ans.append(q[-1])
			else:
				ans.append(0)
			i += 1
			j += 1
	return ans


def printFirstNegativeInteger(A, N, K):
	res = []
	(i, j) = (0, 0)
	temp = []
	while j < N:
		if A[j] < 0:
			temp.append(A[j])
		if j - i + 1 < K:
			j += 1
		elif j - i + 1 == K:
			if temp == []:
				res.append(0)
			else:
				res.append(temp[0])
				if A[i] == temp[0]:
					temp.remove(temp[0])
			i += 1
			j += 1
	return res


def printFirstNegativeInteger(A, N, K):
	result = []
	queue = []
	for i in range(K):
		if A[i] < 0:
			queue.append(A[i])
	if queue:
		result.append(queue[0])
	else:
		result.append(0)
	for i in range(K, N):
		if queue and queue[0] == A[i - K]:
			queue.pop(0)
		if A[i] < 0:
			queue.append(A[i])
		if queue:
			result.append(queue[0])
		else:
			result.append(0)
	return result


def printFirstNegativeInteger(A, N, K):
	l = []
	firstNegativeIndex = 0
	for i in range(K - 1, N):
		while firstNegativeIndex < i and (firstNegativeIndex <= i - K or A[firstNegativeIndex] > 0):
			firstNegativeIndex += 1
		firstElement = A[firstNegativeIndex] if A[firstNegativeIndex] < 0 else 0
		l.append(firstElement)
	return l


from collections import deque

def printFirstNegativeInteger(arr, n, k):
	ans = []
	dq = deque()
	for i in range(k):
		if arr[i] < 0:
			dq.append(i)
	if dq:
		ans.append(arr[dq[0]])
	else:
		ans.append(0)
	for i in range(k, n):
		while dq and i - k + 1 > dq[0]:
			dq.popleft()
		if arr[i] < 0:
			dq.append(i)
		if dq:
			ans.append(arr[dq[0]])
		else:
			ans.append(0)
	return ans


from collections import deque

def printFirstNegativeInteger(arr, n, k):
	result = []
	negative_numbers = deque()
	for i in range(k):
		if arr[i] < 0:
			negative_numbers.append(i)
	if negative_numbers:
		result.append(arr[negative_numbers[0]])
	else:
		result.append(0)
	for i in range(k, n):
		while negative_numbers and negative_numbers[0] < i - k + 1:
			negative_numbers.popleft()
		if arr[i] < 0:
			negative_numbers.append(i)
		if negative_numbers:
			result.append(arr[negative_numbers[0]])
		else:
			result.append(0)
	return result


from collections import deque

def printFirstNegativeInteger(A, N, K):
	queue = deque()
	ans = []
	i = 0
	while i < K:
		if A[i] < 0:
			queue.append(i)
		i += 1
	if queue:
		ans.append(A[queue[0]])
	else:
		ans.append(0)
	while i < N:
		if queue and i - queue[0] >= K:
			queue.popleft()
		if A[i] < 0:
			queue.append(i)
		if queue:
			ans.append(A[queue[0]])
		else:
			ans.append(0)
		i += 1
	return ans


def printFirstNegativeInteger(A, N, K):
	temp = list()
	result = list()
	i = 0
	j = 0
	while j < N:
		if j - i + 1 < K:
			if A[j] < 0:
				temp.append(A[j])
		elif j - i + 1 == K:
			if A[j] < 0:
				temp.append(A[j])
			if len(temp) > 0:
				result.append(temp[0])
				if A[i] == temp[0]:
					temp.pop(0)
			else:
				result.append(0)
			i += 1
		j += 1
	return result


def printFirstNegativeInteger(A, N, K):
	i = 0
	l = []
	result = []
	start = 0
	while i < N:
		if A[i] < 0:
			l.append(A[i])
		if i >= K - 1:
			if len(l) > 0:
				result.append(l[0])
			else:
				result.append(0)
			if A[start] < 0:
				del l[0]
			start += 1
		i += 1
	return result


def printFirstNegativeInteger(A, N, K):
	i = 0
	low = 0
	high = K - 1
	lst = []
	while high < N:
		if i > high:
			lst.append(0)
			low += 1
			high += 1
		elif A[i] < 0 and i >= low and (i <= high):
			lst.append(A[i])
			low += 1
			high += 1
		else:
			i += 1
	return lst


def printFirstNegativeInteger(A, N, K):
	from collections import deque
	(i, j) = (0, 0)
	re = []
	dq = deque()
	while j < N:
		if A[j] < 0:
			dq.append(j)
		if len(dq) > 0 and dq[0] < i:
			dq.popleft()
		if j - i + 1 < K:
			j += 1
		elif j - i + 1 == K:
			if len(dq) > 0:
				re.append(A[dq[0]])
			else:
				re.append(0)
			i += 1
			j += 1
	return re


def printFirstNegativeInteger(A, N, K):
	(i, j) = (0, 0)
	(l, h) = (0, K - 1)
	sol = [0] * (N - K + 1)
	while h < N:
		if i > h:
			j += 1
			l += 1
			h += 1
		elif A[i] < 0 and i > l - 1 and (i < h + 1):
			sol[j] = A[i]
			j += 1
			l += 1
			h += 1
		else:
			i += 1
	return sol


def printFirstNegativeInteger(arr, n, k):
	n = len(arr)
	i = 0
	j = 0
	neg = []
	ans = []
	while i <= n - 1:
		if arr[i] < 0:
			neg.append(arr[i])
		if i < k - 1:
			i += 1
		else:
			ans.append(neg[0]) if len(neg) > 0 else ans.append(0)
			if arr[j] < 0:
				neg.pop(0)
			i += 1
			j += 1
	return ans


from collections import *

def printFirstNegativeInteger(arr, n, k):
	(i, j) = (0, 0)
	(win, l, ans) = ([], [], [])
	while i < len(arr) - k + 1:
		win.append(arr[j])
		if arr[j] < 0:
			l.append(arr[j])
		if j - i + 1 == k:
			if l:
				ans.append(l[0])
			else:
				ans.append(0)
			k1 = win.pop(0)
			if l and l[0] == k1:
				l.pop(0)
			i += 1
		j += 1
	return ans


def printFirstNegativeInteger(A, N, K):
	q = []
	res = [0] * (N - K + 1)
	for i in range(N):
		if A[i] < 0:
			q.append(i)
	for i in range(N - K + 1):
		if len(q) > 0 and q[0] < i:
			q.pop(0)
		if len(q) > 0 and q[0] <= i + K - 1:
			res[i] = A[q[0]]
		elif len(q) == 0:
			res[i] = 0
		else:
			res[i] = 0
	return res


def printFirstNegativeInteger(A, N, K):
	i = 0
	ls = []
	v = []
	j = 0
	while j < N:
		if A[j] < 0:
			ls.append(A[j])
		if j - i + 1 < K:
			j += 1
		elif j - i + 1 == K:
			if len(ls) == 0:
				v.append(0)
			else:
				v.append(ls[0])
				if A[i] == ls[0]:
					ls = ls[1:]
			i += 1
			j += 1
	return v


def printFirstNegativeInteger(A, N, K):
	slidingWindow = []
	answers = []
	for i in range(K):
		if A[i] < 0:
			slidingWindow.append([i, A[i]])
	for j in range(K, N):
		if len(slidingWindow) == 0:
			answers.append(0)
		else:
			answers.append(slidingWindow[0][1])
		if len(slidingWindow) > 0 and j - K + 1 > slidingWindow[0][0]:
			slidingWindow.pop(0)
		if A[j] < 0 and len(slidingWindow) < K:
			slidingWindow.append([j, A[j]])
	if len(slidingWindow) > 0:
		answers.append(slidingWindow[0][1])
	else:
		answers.append(0)
	return answers


from collections import deque

def printFirstNegativeInteger(A, N, K):
	ans = []
	i = j = 0
	q = deque()
	while j < N:
		if A[j] < 0:
			q.append(A[j])
		if j - i + 1 < K:
			j += 1
		else:
			if q:
				ans.append(q[0])
			else:
				ans.append(0)
			if A[i] < 0:
				q.popleft()
			i += 1
			j += 1
	return ans


from collections import deque

def printFirstNegativeInteger(A, N, K):
	i = 0
	j = 0
	neg = deque()
	res = []
	while j < N:
		if A[j] < 0:
			neg.append(A[j])
		if j - i + 1 < K:
			j += 1
		elif j - i + 1 == K:
			if neg:
				res.append(neg[0])
				if A[i] == neg[0]:
					neg.popleft()
			else:
				res.append(0)
			i += 1
			j += 1
	return res


from collections import deque

def printFirstNegativeInteger(arr, n, k):
	ans = []
	q = deque()
	(i, j) = (0, 0)
	while j < n:
		if arr[j] < 0:
			q.append(arr[j])
		if j - i + 1 < k:
			j += 1
		elif j - i + 1 == k:
			if not q:
				ans.append(0)
			else:
				ans.append(q[0])
				if arr[i] < 0:
					q.popleft()
			i += 1
			j += 1
	return ans


from collections import deque

def printFirstNegativeInteger(A, N, K):
	queue = deque()
	result = []
	left = 0
	for i in range(0, K):
		if A[i] < 0:
			queue.append(A[i])
	if queue:
		result.append(queue[0])
		if queue[0] == A[left]:
			queue.popleft()
	else:
		result.append(0)
	left = 1
	right = K
	while right < N:
		if A[right] < 0:
			queue.append(A[right])
		if not queue:
			result.append(0)
		if queue:
			result.append(queue[0])
			if queue[0] == A[left]:
				queue.popleft()
		left = left + 1
		right = right + 1
	return result


def printFirstNegativeInteger(A, N, K):
	ws = we = 0
	l = []
	q = []
	while we < N:
		if A[we] < 0:
			q.append(A[we])
		if we - ws + 1 < K:
			we += 1
		elif we - ws + 1 == K:
			if len(q) == 0:
				l.append(0)
			else:
				l.append(q[0])
				if A[ws] < 0:
					q.pop(0)
			ws += 1
			we += 1
	return l


def printFirstNegativeInteger(arr, n, k):
	lci = -1
	lni = -1
	ans = []
	for i in range(0, n - k + 1):
		if lni < i:
			for j in range(lci + 1, i + k):
				lci += 1
				if arr[j] < 0:
					lni = j
					ans.append(arr[j])
					break
			else:
				ans.append(0)
		else:
			ans.append(ans[-1])
	return ans


def printFirstNegativeInteger(A, N, k):
	stack = []
	i = j = 0
	res = []
	while j < N:
		if A[j] < 0:
			stack.append(A[j])
		if j - i == k - 1:
			if len(stack) <= 0:
				res.append(0)
			else:
				res.append(stack[0])
				if stack[0] == A[i]:
					stack.pop(0)
			i += 1
		j += 1
	return res


def printFirstNegativeInteger(A, N, K):
	(Q, ans) = ([], [])
	i = 0
	while i < N:
		if A[i] < 0:
			Q.append(i)
		i += 1
		if i >= K:
			if Q == []:
				ans.append(0)
			else:
				ans.append(A[Q[0]])
				if Q[0] == i - K:
					Q.pop(0)
	return ans


def printFirstNegativeInteger(A, N, K):
	Q = []
	ans = []
	for i in range(N):
		if i >= K:
			if Q != []:
				ans.append(A[Q[0]])
				if Q[0] == i - K:
					Q.pop(0)
			else:
				ans.append(0)
		if A[i] < 0:
			Q.append(i)
	if Q != []:
		ans.append(A[Q[0]])
	else:
		ans.append(0)
	return ans


def printFirstNegativeInteger(a, n, k):
	ans = []
	from collections import deque
	b = deque()
	for i in range(k - 1):
		if a[i] < 0:
			b.append(a[i])
	i = 0
	j = k - 1
	while j < n:
		if a[j] < 0:
			b.append(a[j])
		if len(b) > 0:
			ans.append(b[0])
		else:
			ans.append(0)
		if len(b) > 0 and a[i] == b[0]:
			b.popleft()
		i += 1
		j += 1
	return ans


def printFirstNegativeInteger(A, N, K):
	i = 0
	j = 0
	result = []
	l = []
	while j < N:
		if A[j] < 0:
			l.append(A[j])
		if j - i + 1 < K:
			j = j + 1
		elif j - i + 1 == K:
			if len(l) == 0:
				result.append(0)
			elif A[i] == l[0]:
				result.append(l[0])
				l.remove(l[0])
			else:
				result.append(l[0])
			i = i + 1
			j = j + 1
	return result


def printFirstNegativeInteger(A, N, K):
	arr = []
	q = []
	(i, j) = (0, 0)
	while j < N:
		if A[j] < 0:
			q.append(A[j])
		if j - i + 1 < K:
			j += 1
		elif j - i + 1 == K:
			if len(q) == 0:
				arr.append(0)
			else:
				arr.append(q[0])
				if A[i] == q[0]:
					q.pop(0)
			i += 1
			j += 1
	return arr


def printFirstNegativeInteger(arr, n, k):
	queue = []
	res = []
	for i in range(k):
		if arr[i] < 0:
			queue.append(arr[i])
	if queue:
		res.append(queue[0])
	else:
		res.append(0)
	for i in range(k, n):
		if arr[i - k] < 0:
			queue.pop(0)
		if arr[i] < 0:
			queue.append(arr[i])
		if queue:
			res.append(queue[0])
		else:
			res.append(0)
	return res


from collections import *

def printFirstNegativeInteger(A, N, K):
	(i, j) = (0, 0)
	x = deque()
	ans = list()
	while j < len(A):
		if A[j] < 0:
			x.append(A[j])
		if j - i + 1 < K:
			j += 1
		elif j - i + 1 == K:
			if x:
				ans.append(x[0])
				if A[i] == x[0]:
					x.popleft()
			else:
				ans.append(0)
			i += 1
			j += 1
	return ans


def printFirstNegativeInteger(A, N, K):
	l = []
	n = []
	for i in range(K - 1):
		if A[i] < 0:
			n.append(A[i])
	for i in range(K - 1, N):
		if A[i] < 0:
			n.append(A[i])
		if len(n) != 0:
			l.append(n[0])
			if n[0] == A[i - K + 1]:
				n.pop(0)
		else:
			l.append(0)
	return l


def printFirstNegativeInteger(A, N, K):
	firstNegativeNumbers = [0] * (N - K + 1)
	dq = []
	windowStart = windowEnd = idx = 0
	for i in range(windowEnd, N):
		if A[i] < 0:
			dq.append(A[i])
		if i - windowStart + 1 == K:
			if len(dq) == 0:
				firstNegativeNumbers[idx] = 0
				idx += 1
			else:
				num = dq[0]
				firstNegativeNumbers[idx] = num
				idx += 1
				if num == A[windowStart]:
					dq.pop(0)
			windowStart += 1
	return firstNegativeNumbers


from collections import *

def printFirstNegativeInteger(arr, N, K):
	l = deque()
	i = 0
	j = 0
	ans = []
	while i < N - K + 1:
		if arr[j] < 0:
			l.append(arr[j])
		if j - i + 1 == K:
			if l:
				ans.append(l[0])
			else:
				ans.append(0)
			if l:
				if arr[i] == l[0]:
					l.popleft()
			i += 1
		j += 1
	return ans


def printFirstNegativeInteger(A, N, K):
	(start, end) = (0, 0)
	neg = []
	result = []
	while end < N:
		if A[end] < 0:
			neg.append(A[end])
		if end - start + 1 < K:
			end += 1
		elif end - start + 1 == K:
			if len(neg) > 0:
				result.append(neg[0])
				if A[start] == neg[0]:
					neg.pop(0)
			else:
				result.append(0)
			start += 1
			end += 1
	return result


def printFirstNegativeInteger(A, N, K):
	l = []
	ans = []
	for i in range(K - 1):
		if A[i] < 0:
			l.append(A[i])
	for (i, j) in enumerate(range(K - 1, N)):
		if A[j] < 0:
			l.append(A[j])
		if not l:
			ans.append(0)
		else:
			ans.append(l[0])
		if l and l[0] == A[i]:
			l.pop(0)
	return ans


import queue

def printFirstNegativeInteger(A, N, K):
	s = []
	ans = []
	for i in range(K):
		if A[i] < 0:
			s.append(i)
	if len(s) != 0:
		ans.append(A[s[0]])
	else:
		ans.append(0)
	for i in range(K, N):
		if len(s) > 0 and i - s[0] >= K:
			s.pop(0)
		if A[i] < 0:
			s.append(i)
		if len(s) != 0:
			ans.append(A[s[0]])
		else:
			ans.append(0)
	return ans


def printFirstNegativeInteger(A, N, K):
	(i, j) = (0, 0)
	lst = []
	ans = []
	while j < N:
		if A[j] < 0:
			lst.append(A[j])
		if j - i + 1 < K:
			j += 1
		elif j - i + 1 == K:
			if len(lst) == 0:
				ans.append(0)
			else:
				ans.append(lst[0])
				if lst[0] == A[i]:
					lst.remove(lst[0])
			i += 1
			j += 1
	return ans


def printFirstNegativeInteger(A, N, K):
	ans = []
	q = []
	(wstart, wend) = (0, 0)
	while wend < len(A):
		if A[wend] < 0:
			q.append(A[wend])
		if wend - wstart + 1 == K:
			if len(q) == 0:
				ans.append(0)
			else:
				ans.append(q[0])
				if A[wstart] == q[0]:
					q.pop(0)
			wstart += 1
		wend += 1
	return ans


from collections import deque

def printFirstNegativeInteger(A, N, K):
	q = deque()
	ans = []
	for i in range(K):
		if A[i] < 0:
			q.append(A[i])
	start = 0
	end = K - 1
	while end < N:
		if q:
			ans.append(q[0])
		else:
			ans.append(0)
		if q and A[start] == q[0]:
			q.popleft()
		start += 1
		end += 1
		if end == N:
			return ans
		if A[end] < 0:
			q.append(A[end])


from collections import deque

def printFirstNegativeInteger(A, N, K):
	q = deque()
	neg = []
	(i, j) = (0, K - 1)
	for x in range(K):
		if A[x] < 0:
			q.append(A[x])
	while j < N:
		if len(q) == 0:
			neg.append(0)
		else:
			neg.append(q[0])
			if A[i] == q[0]:
				q.popleft()
		i += 1
		if j == N - 1:
			break
		j += 1
		if A[j] < 0:
			q.append(A[j])
	return neg


def printFirstNegativeInteger(A, N, K):
	(i, j) = (0, 0)
	nlist = []
	flist = []
	while j < len(A):
		if A[j] < 0:
			nlist.append(A[j])
		if j - i + 1 < K:
			j += 1
		elif j - i + 1 == K:
			if len(nlist) > 0:
				flist.append(nlist[0])
				if nlist[0] == A[i]:
					nlist.pop(0)
			else:
				flist.append(0)
			i += 1
			j += 1
	return flist


from collections import deque

def printFirstNegativeInteger(A, N, k):
	neg_arr = deque()
	(i, j) = (0, 0)
	ans = []
	while j < N:
		if A[j] < 0:
			neg_arr.append(A[j])
		if j - i + 1 == k:
			if len(neg_arr):
				ans.append(neg_arr[0])
				if A[i] == neg_arr[0]:
					neg_arr.popleft()
			else:
				ans.append(0)
			i += 1
		j += 1
	return ans


def printFirstNegativeInteger(A, N, K):
	i = j = 0
	res = []
	c = 0
	neg = []
	while j < N:
		c += 1
		if A[j] < 0:
			neg.append(j)
		if c == K:
			val = 0
			i += 1
			if len(neg) > 0:
				ind = neg[0]
				val = A[ind]
				if ind < i:
					neg.pop(0)
			res.append(val)
			c -= 1
		j += 1
	return res


def printFirstNegativeInteger(A, N, K):
	start = 0
	end = K - 1
	window = []
	for i in range(K):
		if A[i] < 0:
			window.append(A[i])
	ans = []
	if len(window) > 0:
		ans.append(window[0])
	else:
		ans.append(0)
	end += 1
	while end < N:
		if A[end] < 0:
			window.append(A[end])
		if A[start] < 0:
			window.pop(0)
		if len(window) > 0:
			ans.append(window[0])
		else:
			ans.append(0)
		start += 1
		end += 1
	return ans


def printFirstNegativeInteger(A, N, K):
	arr = []
	neg = []
	count = 0
	val = []
	negative_present = False
	i = 0
	while i < K:
		if A[i] < 0:
			if count == 0:
				val.append(A[i])
			count += 1
			neg.append(A[i])
		arr.append(A[i])
		i = i + 1
	if neg == []:
		val.append(0)
	for i in range(K, N):
		temp = arr.pop(0)
		if temp < 0:
			neg.pop(0)
		ele = A[i]
		if ele < 0:
			neg.append(ele)
		arr.append(A[i])
		if neg == []:
			val.append(0)
		else:
			val.append(neg[0])
	return val


from collections import deque

def printFirstNegativeInteger(A, N, K):
	d = deque()
	for i in range(N):
		if A[i] < 0:
			d.append(i)
	ptr1 = 0
	ptr2 = K
	lst = list()
	while ptr2 <= N:
		if len(d):
			x = d.popleft()
		else:
			x = None
		if x != None and x >= ptr1 and (x < ptr2):
			while ptr2 <= N and x >= ptr1 and (ptr2 > x):
				lst.append(A[x])
				ptr1 += 1
				ptr2 += 1
		else:
			d.appendleft(x)
			lst.append(0)
			ptr1 += 1
			ptr2 += 1
	return lst


def printFirstNegativeInteger(A, N, K):
	negs = []
	ans = [0] * (N - K + 1)
	for i in range(N):
		if A[i] < 0:
			negs.append(i)
	j = 0
	for i in range(N - K + 1):
		if j < len(negs) and negs[j] >= i and (negs[j] < i + K):
			ans[i] = A[negs[j]]
			if negs[j] == i:
				j += 1
		else:
			ans[i] = 0
	return ans


def printFirstNegativeInteger(a, n, k):
	q = []
	i = 0
	j = 0
	ans = []
	while j < n:
		if a[j] < 0:
			q.append(a[j])
		if j - i + 1 < k:
			j += 1
		elif j - i + 1 == k:
			if len(q) == 0:
				ans.append(0)
			else:
				ans.append(q[0])
				if a[i] == q[0]:
					q.pop(0)
			i = i + 1
			j = j + 1
	return ans


def first_negative_number(input_arr: [], n, k):
	output_arr = []
	input_data_queue = []
	for i in range(n):
		if input_arr[i] < 0:
			input_data_queue.append(i)
	if len(input_data_queue) == 0:
		return [0] * (n - k + 1)
	start = 0
	end = k - 1
	while end < n:
		if len(input_data_queue) == 0:
			output_arr.append(0)
			start = start + 1
			end = end + 1
			continue
		curr_negative_index = input_data_queue[0]
		if start <= curr_negative_index <= end:
			output_arr.append(input_arr[curr_negative_index])
		else:
			output_arr.append(0)
		if start == curr_negative_index:
			input_data_queue.pop(0)
		start = start + 1
		end = end + 1
	return output_arr

def printFirstNegativeInteger(A, N, K):
	return first_negative_number(A, N, K)


def printFirstNegativeInteger(A, N, K):
	q = []
	ans = []
	for i in range(K):
		if A[i] < 0:
			q.append(A[i])
	if q:
		ans.append(q[0])
	else:
		ans.append(0)
	j = 0
	for i in range(K, N):
		if q:
			if q[0] == A[j]:
				q.remove(q[0])
		j += 1
		if A[i] < 0:
			q.append(A[i])
		if q:
			ans.append(q[0])
		else:
			ans.append(0)
	return ans


def printFirstNegativeInteger(A, N, K):
	qu = []
	for i in range(N):
		if A[i] < 0:
			qu.append(i)
	res = [0 for _ in range(N - K + 1)]
	resIdx = 0
	start = K - 1
	while start < N:
		if len(qu) <= 0:
			break
		while len(qu) and start - qu[0] + 1 > K:
			qu.pop(0)
		if len(qu) and qu[0] <= start:
			res[resIdx] = A[qu[0]]
		resIdx += 1
		start += 1
	return res


from collections import deque

def printFirstNegativeInteger(A, N, K):
	ans = []
	q = deque()
	for index in range(K):
		if A[index] < 0:
			q.append(index)
	if len(q) > 0:
		ans.append(A[q[0]])
	else:
		ans.append(0)
	for index in range(K, N):
		if len(q) > 0 and index - q[0] >= K:
			q.popleft()
		if A[index] < 0:
			q.append(index)
		if len(q) > 0:
			ans.append(A[q[0]])
		else:
			ans.append(0)
	return ans


def printFirstNegativeInteger(s, n, k):
	p = []
	h = k - 1
	l = 0
	n = len(s)
	ps = []
	for i in range(k):
		if s[i] < 0:
			p.append(s[i])
	while h < n:
		if p:
			ps.append(p[0])
		else:
			ps.append(0)
		if s[l] < 0:
			p.pop(0)
		l += 1
		if h == n - 1:
			break
		else:
			h += 1
		if s[h] < 0:
			p.append(s[h])
	return ps


def printFirstNegativeInteger(a, n, k):
	c = [0] * (n - k + 1)
	b = []
	t = 1
	for i in range(n):
		if a[i] < 0:
			b.append(i)
	for j in range(k):
		if b and j == b[0]:
			c[0] = a[j]
			break
	j = k
	for i in range(1, n - k + 1):
		if b and b[0] < i:
			b.remove(b[0])
		if b and b[0] >= i and (b[0] <= j):
			c[t] = a[b[0]]
		if not b:
			break
		i += 1
		j += 1
		t += 1
	return c