Ones

Time limit2.5sMemory limit1024 MB

Summary

Find where the longest run of 1s sits in a hidden bit array, using as few flip-and-query rounds as possible, where each query returns only the new longest run length.

Level: Medium6 of 10
Topics: Array, Binary search, Divide and conquer
Solved: No attempts yet

Problem

There is a hidden array of $N$ bits $a_0, \dots, a_{N-1}$ . In one query, you can choose a subset of positions in the sequence and flip the bits at those positions. Flipping a $0$ bit changes it to a $1$ , and flipping a $1$ bit turns it into a $0$ . After each query, you are given the length of the longest consecutive subarray of $1$ s in the new array. A flipped bit stays flipped until a later query flips it back.

You want to find where the longest subarray of ones is located after all queries (or any one of them, if several exist). Write a program that does this in as few queries as possible.

Constraints

$1 \le N \le 10^4$
$0 \le a_i \le 1$
$T = 5$

Examples1

Example 1
Input
```
1
0
```
Expected output
```
0 -1
```