A. Cereal Sort
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Jesse has $$$n$$$ red pandas. Each of them is assigned an integer ID number. It is possible that multiple red pandas have the same ID number.

He asks them to form a single-file line sorted by ID number, but due to copious confusion, they line up in a random order! Unsure of what to do, Jesse consults his friend Jerry for help, who claims to have a perfect idea: the Cereal Sorter, a device he recently invented!

First, the Cereal Sorter will create a new empty line. Then, while there are still red pandas in the first line, it does the following:

  • First, it scans through the first line in $$$k$$$ seconds, where $$$k$$$ is the number of red pandas in the first line.
  • Let $$$m$$$ be the minimum ID of a red panda in the first line. The Sorter instantly removes all red pandas with ID $$$m$$$ from the first line and teleports them to the end of the second line.

See the notes for a better understanding of this process.

Jesse is convinced that this process may take a long time, as it seems quite complex. Please help him out by determining how many seconds the sorting operation will take!

Input

The first line contains $$$n$$$, the number of red pandas ($$$1 \le n \le 10^6$$$).

The second line of input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, the IDs of the red pandas ($$$1 \le a_i \le 10^6$$$).

Output

Output the answer on a single line.

Examples
Input
4
3 2 2 1
Output
8
Input
5
1 8 8 8 1000000
Output
10
Note

In the first test, the process goes like this:

  • Initially, the first line is $$$[3, 2, 2, 1]$$$ and the second line is $$$[]$$$.
  • The Sorter scans through the first line in $$$4$$$ seconds. The minimum ID in the first line is $$$1$$$, so it moves the red panda with ID $$$1$$$ to the second line. The first line is now $$$[3, 2, 2]$$$, and the second line is now $$$[1]$$$.
  • The Sorter scans through the first line in $$$3$$$ seconds. The minimum ID in the first line is $$$2$$$, so it moves the red pandas with ID $$$2$$$ to the second line. The first line is now $$$[3]$$$, and the second line is now $$$[1, 2, 2]$$$.
  • The Sorter scans through the first line in $$$1$$$ second. The minimum ID in the first line is $$$3$$$, so it moves the red panda with ID $$$3$$$ to the second line. The first line is now $$$[]$$$, and the second line is now $$$[1, 2, 2, 3]$$$.

In total, this takes $$$4+3+1=8$$$ seconds.

Problem Credits: Aryansh Shrivastava