Intersegment Activation

This is an interactive problem.

There is an array of $n$ cells, numbered from $1$ to $n$. For each pair of integers $(i, j)$ with $1 \le i \le j \le n$, there is a barrier covering all cells from $i$ to $j$, inclusive. Each barrier is either active or inactive. A cell is visible if no active barrier covers it. Otherwise, the cell is invisible.

The state of each barrier is unknown to you. You can only observe the number of visible cells. You can flip the state of any barrier: an active barrier becomes inactive, and an inactive barrier becomes active. Your task is to make all barriers inactive, so that all cells become visible.

In the example, initially only two barriers, $(1, 2)$ and $(2, 3)$, are active. Together they cover all three cells, so $k$ is $0$ in the first round.

• After flipping barrier $(2, 2)$, there are three active barriers, and still $0$ visible cells, so $k$ is $0$.
• After flipping barrier $(1, 2)$, cell $1$ becomes visible, so $k$ is $1$.
• After flipping barrier $(2, 3)$, cell $3$ also becomes visible. The only invisible cell is cell $2$, covered by the only active barrier $(2, 2)$, so $k$ is $2$.
• After flipping barrier $(2, 2)$, all barriers are inactive and all cells are visible. After reading $k = 3$, the program terminates.