E. Chaves and habibi arrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Some time ago, Chaves was walking through the Egyptian market, where many vendors offered him products with great discounts. Chaves was captivated by certain arrangements of numbers, called "habibi arrays."

A habibi array of $$$N$$$ elements is an array of distinct numbers where each number is between 1 and $$$10^9$$$. For example, if $$$N = 3$$$, the array $$$[3, 7, 2]$$$ is a habibi array, but the array $$$[3, 3, 2]$$$ is not (because the number 3 is repeated).

Chaves, being an excellent negotiator, offered $0.00001 in cash for one of the habibi arrays. However, the Egyptian vendor indicated that the price of a habibi array must be calculated in a more elaborate way.

To determine the price, we define that an array of $$$N$$$ distinct elements $$$A_1, \ldots, A_N$$$ is melo if we can write the sorted array in ascending order using a stack and $$$2N$$$ operations, where:

In the $$$i$$$-th operation could be of the types:

  1. We add to the stack the first elemento of the array that hasn't been added to the stack, from left to right.
  2. We remove the top element of the stack and write this element in the first empty space of the new array, from left to right.

If at the end of the process, the written numbers are sorted in ascending order and the stack is empty, then the array is melo. For example, the array $$$[3, 2, 1]$$$ is melo because, after three operations of the first kind, the stack becomes $$$[3, 2, 1]$$$ with 1 at the top. We could then remove the top element three times, leaving us with the new array $$$[1, 2, 3]$$$, which is sorted in ascending order.

Other examples:

  • The array $$$[2, 1, 3]$$$ is melo because we can push 2 and 1 onto the stack, then pop 1 and 2 (writing them in order), and finally push and pop 3.
  • The array $$$[1, 2, 3]$$$ is melo because we can push and pop each element in each operation.

A stack is a data structure that operates in a last-in, first-out (LIFO) manner. Elements are added (pushed) to the top and removed (popped) from the top. For example, if we push the elements 1, 2, and 3 onto the stack in that order, the stack will look like this: $$$[1, 2, 3]$$$ (with 3 at the top). If we then pop an element, we will remove 3, and the stack will become $$$[1, 2]$$$.

Finally, the price of a habibi array is the number of melo subarrays it contains. A subarray is a contiguous portion of an array; for example, $$$[1,3]$$$ is a subarray of $$$[1,1,3,2]$$$, but $$$[1,2]$$$ is not.

Given a habibi array, help Chaves determine how much the Egyptian vendor will charge him.

Input

The input consists of an integer $$$1 \leq N \leq 10^6$$$ and a habibi array of $$$N$$$ elements, where each element is distinct and between 1 and $$$10^9$$$.

Output

Print the number of melo subarrays in the given array.

Example
Input
4
2 4 3 1
Output
9
Note

The only subarray that is not melo is $$$[2, 4, 3, 1]$$$ (note that an array is a subarray of itself).