**********************************************************************
                           BRONZE PROBLEMS
**********************************************************************
                  Three problems numbered 11 through 13
**********************************************************************

Problem 11: Stump Removal [Graham Poulter, 2005]

Always thinking of the cows' grazing experience, FJ has found that
he must remove N (1 <= N <= 50,000) unsightly stumps from the
pasture. The stumps are conveniently arranged in a straight line
and numbered 1..N with each stump having some height H_i (1 <= H_i
<= 10,000).

FJ will use the traditional high explosives to destroy the stumps.
These high explosives are formulated to destroy adjacent stumps as
long as those adjacent stumps are strictly shorter than the nearest
stump being destroyed. The blast can continue past the closest
adjacent stump to the next adjacent stump if it is even shorter
than the nearest stump just destroyed.  As soon as a stump encountered
by the blast wave is not shorter, though, no more destruction occurs
on that side of the target stump (the other side follows the same
rules with whatever stumps might appear there).

Consider a line of nine stumps with these heights:

              1 2 5 4 3 3 6 6 2

If FJ blows up the third stump (with height 5), then the second
stump will also be destroyed (height 2) and the first stump (height
1) will also be destroyed. Likewise, the fourth stump (height 4)
and fifth stump (height 3) will be destroyed since they are
successively shorter, leaving the line like this:

              * * * * * 3 6 6 2

Two more explosives (at stumps 7 and 8) will destroy the rest.

Help FJ determine the minimum number of explosive charges he needs
to destroy the stumps.

PROBLEM NAME: stumps

INPUT FORMAT:

* Line 1: A single integer, N

* Lines 2..N+1: Line i+1 contains H_i

SAMPLE INPUT (file stumps.in):

9
1
2
5
4
3
3
6
6
2

OUTPUT FORMAT:

* Lines 1..?: Each line contains one integer which is the index of a
        stump to blow up. The indices must be listed in increasing
        order.

SAMPLE OUTPUT (file stumps.out):

3
7
8

**********************************************************************

Problem 12: Finicky Grazers [Osman, 2005]

Farmer John's N (1 <= N <= 10,000) cows (conveniently numbered 1..N)
graze in a straight line in their pasture whose length is L+1 (N
<= L <= 100,000) meters. Every morning, they place themselves at
various unique integer locations along that line. FJ has observed
that the cows produce more milk when the distance to the other
grazing cows is maximized.

Always the enterprising farmer, FJ wants to maximize the distance
between each and every pair of neighboring cows by moving the cows
to the right or left, but always with integer inter-cow spacing and
never changing their order on the line. He spends 1 minute to move
a cow 1 meter. When he's finished, he knows that the distances
between every adjacent pair of cows will be one of two integers: D
or D+1.

Help FJ to calculate minimum time he needs to arrange the positions
of the cows.

PROBLEM NAME: graze1

INPUT FORMAT:

* Line 1: Two space-separated integers, N and L

* Lines 2..N+1: Line i+1 describes cow i with a single integer (range
        0..L) representing the position of a cow; 0 is the left-most
        position. The list is sorted by position with the smallest
        position value first.

SAMPLE INPUT (file graze1.in):

5 10
0
1
4
9
10

INPUT DETAILS:

The cows are arranged like this at the start:
1 2 - - 3 - - - - 4 5

OUTPUT FORMAT:

* Line 1: A single line with minimum time FJ needs to arrange the
        positions of the  cows.

SAMPLE OUTPUT (file graze1.out):

3

OUTPUT DETAILS:

The cows end up arranged like this:
1 - 2 - 3 - - 4 - - 5
Cow #2 moves from position 1 to position 2 (1 meter).  Cow #4 moves
from position 9 to position 7 (2 meters).  Other cows don't move.
Moving times are 1+2=3, which is the final answer.

**********************************************************************

Problem 13: The Water Bowls [Hal Burch, 2005]

The cows have a line of 20 water bowls from which they drink. The
bowls can be either right-side-up (properly oriented to serve
refreshing cool water) or upside-down (a position which holds no
water). They want all 20 water bowls to be right-side-up and thus
use their wide snouts to flip bowls.

Their snouts, though, are so wide that they flip not only one bowl
but also the bowls on either side of that bowl (a total of three
or -- in the case of either end bowl -- two bowls).

Given the initial state of the bowls (1=undrinkable, 0=drinkable
-- it even looks like a bowl), what is the minimum number of bowl
flips necessary to turn all the bowls right-side-up?

PROBLEM NAME: bowls

INPUT FORMAT:

* Line 1: A single line with 20 space-separated integers

SAMPLE INPUT (file bowls.in):

0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0

OUTPUT FORMAT:

* Line 1: The minimum number of bowl flips necessary to flip all the
        bowls right-side-up (i.e., to 0).  For the inputs given, it
        will always be possible to find some combination of flips that
        will manipulate the bowls to 20 0's.

SAMPLE OUTPUT (file bowls.out):

3

OUTPUT DETAILS:

Flip bowls 4, 9, and 11 to make them all drinkable:
0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [initial state]
0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 4]
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 9]
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [after flipping bowl 11]

**********************************************************************