Input File: antsin.txt
Output File: antsout.txt
Time Limit: 1 second
The world is in peril! Night after night you lose sleep in fear of the imminent threat of global warming. The solution is clear — you must begin breeding ants.
Research suggests that careful observation of the ant species grevana formosae can act as an early warning system for climate change. Specifically, you must examine how many ants are active each day. If the number of active ants is continually increasing, you know that an environmental crisis is near.
1 2 3 2 0 4 2 1
There are two increasing sequences in this list; these are underlined below.
1 2 3 2 0 4 2 1
Note that smaller parts of an increasing sequence do not count (so, for instance, you do not count the smaller sequences 1 2 or 2 3 within the longer 1 2 3). Increasing sequences must also span at least two days (so, for instance, the final 1 on its own does not count). The number of ants in such a sequence must be strictly increasing (so the sequence 2 4 4 7 is not an increasing sequence, since two of its numbers are the same).
Your task is, given the number of active ants over a series of days, to count the total number of increasing sequences.
The first line of input will contain the single integer d, the number of days over which you observe your ants (2 <= d <= 100,000). Following this will be d lines, each containing a single integer. The ith of these lines will contain the number of active ants on the ith day; each of these integers will be between 0 and 10,000 inclusive.
Your output must consist of a single line containing a single integer, which is the total number of increasing sequences.
8 1 2 3 2 0 4 2 1
The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.