INCINT

Problem

You are given a sequence consisting of ~N~ natural numbers: ~A_1~, ~A_2~, ~...~ , ~A_N~. The task is to find the number of intervals of consecutive terms in the sequence that are in (not necessarily strictly) increasing order.

In other words, in how many different ways can we choose two positions ~i~ and ~j~ in the array, where ~1 \le i \le j \le N~, such that ~A_i \le A_{i+1} \le ... \le A_{j-1} \le A_j~.

Input:

The first line of the input will contain an integer ~N~, the number of terms in the sequence. The second line of the input will contain the ~N~ terms of the sequence, separated in pairs by a single space.

Output:

The output should consist of exactly one line containing exactly one integer: the desired number of intervals of consecutive terms in the sequence that are in increasing order.

Constraints

• ~1 \le N \le 1.000.000~.
• ~0 \le A_i \le 1.000.000.000~ για κάθε ~1 \le i \le N~
• Time Limit: ~1~ sec.

• Memory Limit: ~64~ MB.

• For test cases with a total weight of ~30%~, ~N \le 1000~.

• For test cases with a total weight of ~50%~, ~N \le 20.000~.

Examples of Input - Output Files:

1st

STDIN (incint.in)

7
10 13 15 12 19 17 17

STDOUT (incint.out)

12

Explanation of the first example

The ~12~ intervals we can choose are:

• ~7~ intervals with only one term (i.e., with ~i = j~): ~10~, ~13~, ~15~, ~12~, ~19~, ~17~, ~17~.
• ~4~ intervals with two terms: ~10 \le 13~, ~13 \le 15~, ~12 \le 19~, ~17 \le 17~.
• ~1~ interval with three terms: ~10 \le 13 \le 15~.

2nd

STDIN (incint.in)

5
5 4 3 2 1

STDOUT (incint.out)

5

Explanation of the second example

The terms of the sequence are in strictly decreasing order, so there are no other intervals we can choose, except for the 5 intervals with only one term (i.e., with ~i = j~): ~5~, ~4~, ~3~, ~2~, ~1~.