**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Three problems numbered 6 through 8
**********************************************************************

Problem 6: Bad Hair Day [Brian Dean, 2006]

Some of Farmer John's N cows (1 <= N <= 80,000) are having a bad
hair day! Since each cow is self-conscious about her messy hairstyle,
FJ wants to count the number of other cows that can see the top of
other cows' heads.

Each cow i has a specified height h[i] (1 <= h[i] <= 1,000,000,000)
and is standing in a line of cows all facing east (to the right in
our diagrams). Therefore, cow i can see the tops of the heads of
cows in front of her (namely cows i+1, i+2, and so on), for as long
as these cows are strictly shorter than cow i.

Consider this example:

        =
=       =
=   -   =           Cows facing right -->
=   =   =
= - = = =
= = = = = =
1 2 3 4 5 6

Cow#1 can see the hairstyle of cows #2, 3, 4
Cow#2 can see no cow's hairstyle
Cow#3 can see the hairstyle of cow #4
Cow#4 can see no cow's hairstyle
Cow#5 can see the hairstyle of cow 6
Cow#6 can see no cows at all!

Let c[i] denote the number of cows whose hairstyle is visible from
cow i; please compute the sum of c[1] through c[N]. For this example,
the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.

TIME LIMIT: 0.5 seconds

PROBLEM NAME: badhair

INPUT FORMAT:

* Line 1: The number of cows, N.

* Lines 2..N+1: Line i+1 contains a single integer that is the height
        of cow i.

SAMPLE INPUT (file badhair.in):

6
10
3
7
4
12
2


INPUT DETAILS:

Six cows stand in a line; heights are 10, 3, 7, 4, 12, 2.

OUTPUT FORMAT:

* Line 1: A single integer that is the sum of c[1] through c[N].

SAMPLE OUTPUT (file badhair.out):

5

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

Problem 7: Big Square [?, 2006]

Farmer John's cows have entered into a competition with Farmer Bob's
cows. They have drawn lines on the field so it is a square grid
with NxN points (2 <= N <= 100), and each cow of the two herds has
positioned herself exactly on a gridpoint. Of course, no two cows
can stand in the same gridpoint.  The goal of each herd is to form
the largest square (not necessarily parallel to the gridlines) whose
corners are formed by cows from that herd.

All the cows have been placed except for Farmer John's cow Bessie.
Determine the area of the largest square that Farmer John's cows
can form once Bessie is placed on the field (the largest square
might not necessarily contain Bessie).

PROBLEM NAME: bigsq

INPUT FORMAT:

* Line 1: A single integer, N

* Lines 2..N+1: Line i+1 describes line i of the field with N
        characters. The characters are: 'J' for a Farmer John cow, 'B'
        for a Farmer Bob cow, and '*' for an unoccupied square. There
        will always be at least one unoccupied gridpoint.

SAMPLE INPUT (file bigsq.in):

6
J*J***
******
J***J*
******
**B***
******


OUTPUT FORMAT:

* Line 1: The area of the largest square that Farmer John's cows can
        form, or 0 if they cannot form any square.

SAMPLE OUTPUT (file bigsq.out):

4

OUTPUT DETAILS:

If Bessie could go where Farmer Bob's cow is, a square of area 8 would be
formed. However, cows cannot share a grid-point, so she must go in row 3,
column 3 to complete the top-left square of area 4.

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

Problem 8: Round Numbers [ICPSC, 1981]

The cows, as you know, have no fingers or thumbs and thus are unable
to play 'Scissors, Paper, Stone' (also known as 'Rock, Paper,
Scissors', 'Ro, Sham, Bo', and a host of other names) in order to
make arbitrary decisions such as who gets to be milked first. They
can't even flip a coin because it's so hard to toss using hooves.

They have thus resorted to "round number" matching. The first cow
picks an integer less than two billion. The second cow does the
same.  If the numbers are both "round numbers", the first cow wins,
otherwise the second cow wins.

A positive integer N is said to be a "round number" if the binary
representation of N has as many or more zeroes than it has ones.
For example, the integer 9, when written in binary form, is 1001.
1001 has two zeroes and two ones; thus, 9 is a round number. The
integer 26 is 11010 in binary; since it has two zeroes and three
ones, it is not a round number.

Obviously, it takes cows a while to convert numbers to binary, so
the winner takes a while to determine.  Bessie wants to cheat and
thinks she can do that if she knows how many "round numbers" are
in a given range.

Help her by writing a program that tells how many round numbers
appear in the inclusive range given by the input (1 <= Start <
Finish <= 2,000,000,000).

PROBLEM NAME: rndnum

INPUT FORMAT:

* Line 1: Two space-separated integers, respectively Start and Finish.

SAMPLE INPUT (file rndnum.in):

2 12


OUTPUT FORMAT:

* Line 1: A single integer that is the count of round numbers in the
        inclusive range Start..Finish

SAMPLE OUTPUT (file rndnum.out):

6

OUTPUT DETAILS:

 2    10  1x0 + 1x1  ROUND
 3    11  0x0 + 2x1  NOT round
 4   100  2x0 + 1x1  ROUND
 5   101  1x0 + 2x1  NOT round
 6   110  1x0 + 2x1  NOT round
 7   111  0x0 + 3x1  NOT round
 8  1000  3x0 + 1x1  ROUND
 9  1001  2x0 + 2x1  ROUND
10  1010  2x0 + 2x1  ROUND
11  1011  1x0 + 3x1  NOT round
12  1100  2x0 + 2x1  ROUND

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