# Problem F

Bar Shelf

*Dictionnaire encyclopédique de l’épicerie et des industries annexes*by Albert Seigneurie, 1904, p. 117. Public domain.

Organ pipes, the von Trapp children, staircases—oh, how
Quark loves these things. For they are neatly arranged
ascending order, the very signal of cleanliness, structure,
*civilisation*. Quark is your fellow bartender at
*Meson*, the longest bar in the galaxy. Were it up to
Quark, the bottles on the bar shelf would all be neatly and
properly ordered, left-to-right, and in ascending order.

You disagree with Quark. As far as you can tell, the bar’s
patrons appreciate *Meson*’s welcoming atmosphere of
carefully orchestrated insouciance. Surely, a certain amount
messiness on the bar shelf is important for that image.

This has led to long discussions between you and Quark about
how messy the shelf can be. He concedes that a bottle placed to
the left of one that is just slightly smaller doesn’t look very
messy at all. On the other hand, you have to admit that very
big size differences do look way too messy. Finally, you have
agreed on the following rule: Three bottles, not necessarily
adjacent, are a *messy trio* if the one to the left is
at least twice as large as the middle one, which in turn is at
least twice as large as the one to the right.

For instance, in the image below, the bottles have height $4$, $5$, $2$, $1$, and $3$, from left to right. The bottles of height $4$, $2$, and $1$ form a messy trio (because $\frac12 \cdot 4 \geq 2\geq 2\cdot 1$), and so do $5$, $2$, and $1$. The messiness of the entire shelf is the number of messy trios, in this case $2$.

## Input

The input consists of two lines. On the first line, the number $n$ of bottles on the shelf, with $n\geq 1$. On the second line, $n$ integers, separated by space, giving the height (in nanometres) of each bottle from left to right. Each height is an integer between $1$ and $10^9$.

## Output

Output a single integer: the messiness of the shelf. Note that this number can be quite large, but no larger than $\binom {n}{3}$, which for our largest input is bounded by $2 \cdot 10^{15}$.

## Scoring

Your score depends on the length of the shelf that you can handle within the time limit. You get one point for $n\leq 100$, another for $n\leq 5\, 000$, and yet another for $n\leq 200\, 000$. The maximum score is $3$ points.

Sample Input 1 | Sample Output 1 |
---|---|

5 4 5 2 1 3 |
2 |

Sample Input 2 | Sample Output 2 |
---|---|

4 10 5 5 2 |
2 |

Sample Input 3 | Sample Output 3 |
---|---|

3 1 2 4 |
0 |