Problem: Ants

Want to try solving this problem? You can submit your code online if you log in or register.

Ants

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.

An increasing sequence is a series of consecutive days for which the number of active ants is strictly increasing. For example, suppose you watch the ants for eight days and obtain the following measurements:

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.

Input

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.

Output

Your output must consist of a single line containing a single integer, which is the total number of increasing sequences.

Sample Input

Sample Output

Scoring

The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.