Hyakkaryouran Summer Rush!

Nagusa

...That should have been all there was to it. But the battle spread far beyond my expectations, and before I knew it, my palms were sweating.

...Simply holding out in our sand fortifications isn't enough. But rushing out to grapple with them is out of the question. If I get wet, it's over.

That is why I brought a single-use net launcher to use from behind our sand cover. I intend to choose exactly one of the remaining people and fire a net at them from a distance. Once hit, they will panic and lose proper control of their water gun.

Our Hyakkaryouran team is holding a separate front, and the $N$ other participants in my field of view are standing in a line from left to right. Each participant $i$ has a health value $H_i$ that I have assessed. If I fire the net at a participant, that participant panics and repeatedly does the following.

• As long as they have not been eliminated and at least one other person has not been eliminated, they repeat the actions below.

• Each time, they randomly choose one person adjacent to them in the line and fight until a health value reaches $0$.

  • The one with the greater health value has their health reduced to the difference between the two values.
  • The one with the smaller health value has their health reduced to $0$.
  • If their health values are equal, both become $0$.

• A person whose health becomes $0$ can no longer resist, falls into the water, and is immediately eliminated.

• When someone is eliminated, they are removed from the line and the remaining people close the gap without changing their order. Thus, who is adjacent to whom may change.

There is only one goal. I need to calculate the smallest possible number of people remaining, by choosing one person to send into a panic. I absolutely cannot lose this battle and fall into the water. No one can find out that I, the strategist of Hyakkaryouran, am afraid of water...!

Time limit

2000 ms

Memory limit

1024 MB

Checker

CUSTOM