Incremental Stay

Let’s translate the story into the thing it actually is.

At every detected time, exactly one person crosses the door. If they enter, the number of people inside goes up by $1$. If they exit, it goes down by $1$.

The museum starts empty and ends empty, so over the $2n$ events we need a sequence of $n$ ups and $n$ downs. Also, for a given limit $k$, the height must always stay between $0$ and $k$.

The total stay time is the area under this height curve. If $h_i$ is the number of people inside after event $i$, then during the whole interval $[a_i,a_{i+1}]$ that number is constant, so the score is

$$\sum_{i=1}^{2n-1} h_i(a_{i+1}-a_i).$$

Same problem, less museum cosplay: build the highest possible valid mountain path.

Key greedy shape

Take any chunk of $2k$ consecutive events, starting when the museum is empty.

With capacity $k$, the best thing is obvious once you stop overthinking it:

$$0,1,2,\ldots,k,k-1,\ldots,1,0.$$

That means:

• first $k$ events are entrances,
• next $k$ events are exits.

Why? All gaps have positive length. Higher occupancy over any gap is always better. So you want to climb as fast as possible until hitting $k$, then stay as high as the step rules allow, and only descend when you must in order to finish the block. Delaying an entrance is just throwing away positive area for no reason. Classic greedy: don’t make the height curve lower if you can legally make it higher.

The value of such a $2k$ block covering events

$$a_l,a_{l+1},\ldots,a_{l+2k-1}$$

is exactly

$$(a_{l+k}+\cdots+a_{l+2k-1})-(a_l+\cdots+a_{l+k-1}).$$

That is because those first $k$ times become entries, and those next $k$ times become exits.

What about all $2n$ events?

For a fixed $k$, repeat full mountains of size $2k$ from left to right:

• events $1 \ldots 2k$ form one mountain of height $k$,
• events $2k+1 \ldots 4k$ form the next,
• and so on.

If there are leftover events, the count must be even because the total is $2n$. Say the leftover size is $2r$, where $0 \le r < k$. Then the final chunk uses a smaller mountain of height $r$:

$$0,1,2,\ldots,r,r-1,\ldots,0.$$

So the answer for $k$ is the sum of block values over these chunks.

This might look slightly suspicious: why are we allowed to reset to $0$ after every block? Could keeping people inside across a boundary help?

No. The greedy mountain over each prefix is already lexicographically as high as possible under the cap and the need to return eventually. Another way to say it: in any $2k$ consecutive events, once you start at $0$, you cannot get more than the mountain area of height $k$. Crossing block boundaries would force some earlier height to be lower or some later descent to happen sooner. Since every gap length is positive, that trade is never useful. The fastest-climb, latest-drop pattern dominates.

Fast computation

Define prefix sums:

$$pref[i] = a_1+a_2+\cdots+a_i.$$

Then the value of a block starting at 0-based index l with half-size len is

$$(a_{l+len}+\cdots+a_{l+2len-1})-(a_l+\cdots+a_{l+len-1}).$$

With prefix sums, that is $O(1)$.

For each $k$:

1. Start at event index 0.
2. While at least 2*k events remain, add a full block of half-size k.
3. If 2*r events remain, add one final block of half-size r.

The harmonic-looking loop is fine:

$$\sum_{k=1}^{n} \frac{n}{k} = O(n\log n).$$

Across all tests, $\sum n \le 2\cdot 10^5$, so this cruises.

Complexity

For one test case, the total work over all $k$ is $O(n\log n)$, and memory is $O(n)$.

Use long long; answers can be around $n\cdot 10^9$, so int will faceplant.