Optimal Circle Segment

At the 8th eJOI, N contestants (an even number) are dancing in a circle performing the Hora dance. Exactly \(\frac{N}{2}\) of the contestants are males and the other half are females. The contestants are numbered from \(0\) to \(N-1\) around the circle in order, where contestant \(i\) is adjacent to contestants \(i-1\) and \(i+1\) (with the special cases that contestant \(0\) is adjacent to \(N-1\) and \(1\)).

You do not know which contestant is male or female. However, during the contest you are only allowed to ask the judge questions. In one question, you are allowed to provide two integers \(L\) and \(R\) with \(0 \le L, R < N\). The judge will then return:

• If \(L \le R\): the number of males in the segment \([L, R]\).
• If \(L > R\): the total number of males in the segments \([L, N-1]\) and \([0, R]\) (i.e. a wrap-around query).

You are given an integer \(K\). Your goal is to determine the starting index \(S\) of a contiguous segment of length \(K\) on the circular arrangement such that the difference between the number of males and females within the segment is minimized. Formally, if the number of males in the segment is \(m\), then the absolute difference is \(|2m - K|\). If there are multiple valid segments, you may output any valid starting index \(S\).

Note: In this version of the problem, the query mechanism is simulated by providing full input data. You will be given the gender information for all contestants.

Input/Output Specification (Offline Version):

The first line contains two integers \(N\) and \(K\) (with \(N\) even and exactly \(\frac{N}{2}\) males in total). The second line contains \(N\) integers (each either 0 or 1), where 1 represents a male and 0 represents a female, listed in the order of the circle. It is guaranteed that the number of 1's is exactly \(\frac{N}{2}\).

Your task is to print a single integer \(S\): the starting index of a contiguous segment of length \(K\) (the segment may wrap around) that minimizes \(|2m - K|\), where \(m\) is the number of males in that segment.

inputFormat

The first line contains two integers \(N\) and \(K\) (\(N\) is even, and there are exactly \(\frac{N}{2}\) males among \(N\) contestants).
The second line contains \(N\) space-separated integers, each being 0 or 1. Here, 1 indicates a male and 0 indicates a female.

outputFormat

Print a single integer \(S\), the starting index of a contiguous segment of length \(K\) (considering the circle) that minimizes the absolute difference between the number of males and females. If there are multiple answers, output any.

sample

6 3
1 0 1 0 0 1

0