Plants Vs Zombies

hard

In a mysterious botanical garden, an unusual phenomenon is occurring. Each plant hosts a colony of zombie ants that produce both poison and antidote. The delicate balance between these substances determines the plants' survival.

Each plant contains a specific number of zombie ants. These ants have a peculiar behavior:

  • Each ant produces a fixed amount of poison that stays within its host plant.
  • Each ant also produces an antidote, but the antidote immediately transfers to the neighboring plant on the right (if such a plant exists).
  • The leftmost plant has a special property—it receives an infinite supply of antidote from an underground spring, ensuring its survival.

Each night, a deadly cycle occurs:

  • If a plant's poison level (determined by its number of ants) exceeds the antidote it receives from its left neighbor, the plant dies and is removed from the garden.
  • After plant deaths, the antidote flow adjusts to the new arrangement before the next night begins.

Input Format:

The first line contains an integer n n (1n105)(1 \leq n \leq 10^5), the number of plants in the garden. The second line contains n n space-separated integers p1,p2,,pn p_1, p_2, \ldots, p_n , where pi p_i (0pi109)(0 \leq p_i \leq 10^9) represents the number of zombie ants in the i i -th plant.

Output Format:

Output a single integer representing the number of nights until plants stop dying.

Examples:

Example 1:

Input:

7
6 5 8 4 7 10 9

Output:

2

Example 2:

Input:

5
3 6 2 7 5

Output:

2

Code

Loading Editor...