#D9769. Sort
Sort
Sort
After entering high school, Takeko, who joined the programming club, gradually became absorbed in the fun of algorithms. Now, when I'm in the second grade, I'd like to participate in Programming Koshien.
At one point, Takeko, who learned about sorting algorithms, tried to design a sorting algorithm herself. The sort algorithm created by Takeko executes the following processing when a column consisting of one or more natural numbers with no duplication between elements is given as input.
- First, select the first element of the column.
- When there is an element immediately before the selected element, compare the selected element with the element immediately before it. If the previous element is larger, move it immediately after the end of the column (figure). Continue this operation until the selected element is at the beginning of the column or the previous element is smaller than the selected element.
- Finish if the selected element is at the end of the column. If not, select a new element immediately after the selected element and return to 2.
Takeko decided to count the number of operations to move the element immediately after the end of the column in order to estimate how much computational time this algorithm would take.
Write a program that takes column information as input and reports the number of operations that move an element immediately after the end of the column.
Input
The input is given in the following format.
N a1 a2 ... aN
The number of elements N (1 ≤ N ≤ 200000) contained in the column is given in the first row. In the second row, the column elements ai (1 ≤ ai ≤ 109) are given in order from the beginning. There is no duplication in element ai.
Output
Outputs the number of operations to move an element immediately after the end of a column in one row.
Examples
Input
6 1 3 6 5 8 2
Output
10
Input
4 4 3 2 1
Output
6
inputFormat
input.
- First, select the first element of the column.
- When there is an element immediately before the selected element, compare the selected element with the element immediately before it. If the previous element is larger, move it immediately after the end of the column (figure). Continue this operation until the selected element is at the beginning of the column or the previous element is smaller than the selected element.
- Finish if the selected element is at the end of the column. If not, select a new element immediately after the selected element and return to 2.
Takeko decided to count the number of operations to move the element immediately after the end of the column in order to estimate how much computational time this algorithm would take.
Write a program that takes column information as input and reports the number of operations that move an element immediately after the end of the column.
Input
The input is given in the following format.
N a1 a2 ... aN
The number of elements N (1 ≤ N ≤ 200000) contained in the column is given in the first row. In the second row, the column elements ai (1 ≤ ai ≤ 109) are given in order from the beginning. There is no duplication in element ai.
outputFormat
Output
Outputs the number of operations to move an element immediately after the end of a column in one row.
Examples
Input
6 1 3 6 5 8 2
Output
10
Input
4 4 3 2 1
Output
6
样例
4
4 3 2 16