409974: GYM103886 A Cereal Sort
Description
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!
InputThe 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$$$).
OutputOutput the answer on a single line.
ExamplesInput4 3 2 2 1Output
8Input
5 1 8 8 8 1000000Output
10Note
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