CerealCodes 2022 Summer Contest |
---|
Finished |
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:
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!
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 the answer on a single line.
4 3 2 2 1
8
5 1 8 8 8 1000000
10
In the first test, the process goes like this:
In total, this takes $$$4+3+1=8$$$ seconds.
Problem Credits: Aryansh Shrivastava
Name |
---|