Find the Smallest Continuous Parking Spots

You are given a parking lot represented by an array of integers, where 1 indicates an occupied parking spot and 0 indicates a vacant one. Your task is to determine the smallest continuous segment of parking spots that can accommodate a given number of cars in one contiguous sequence.

If such a segment exists, output the starting and ending indices (0-indexed) of that segment. Otherwise, output an empty list [].

Formally, let \( A \) be an array of length \( n \) where \( A[i] \in \{0,1\} \), and let \( k \) be the number of cars. Find indices \( i \) and \( j \) satisfying \( 0 \le i \le j < n \) such that the segment \( A[i\ldots j] \) contains at least \( k \) zeroes and \( j-i+1 \) is minimized. If multiple segments exist, the one found first by a sliding window technique is acceptable.

inputFormat

The input is given from standard input (stdin) in the following format:

n
s1 s2 ... sn
k

Here, the first line contains an integer \( n \), which is the number of parking spots. The second line contains \( n \) space-separated integers \( s_1, s_2, \ldots, s_n \) representing the parking status (0 for vacant, 1 for occupied). The third line contains an integer \( k \), representing the number of cars to accommodate.

outputFormat

Output the starting and ending indices of the smallest continuous segment that can fit all the cars. If such a segment exists, print the two integers separated by a space. Otherwise, print [].

9
1 0 0 1 0 0 0 0 1
3

4 6