U Akaki là một bộ bài gồm n quân bài. Mỗi thẻ có chính xác một số nguyên từ 1 đến 100 000 được viết trên đó. Có thể những con số giống nhau được viết trên một số thẻ.
Akaki quyết định sắp xếp tất cả các quân bài trong bộ bài. Để làm điều này, anh ta lần lượt lấy một lá bài trên cùng từ bộ bài và nếu số ghi trên đó bằng số nhỏ nhất trong số tất cả các số còn lại trong bộ bài, thì anh ta đặt lá bài này sang một bên. Nếu không, Akaki đặt lá bài này ở dưới cùng của bộ bài và rút lá bài tiếp theo từ trên cùng của bộ bài. Quá trình kết thúc khi không còn thẻ nào trong bộ bài. Chúng ta có thể cho rằng Akaki bất cứ lúc nào cũng biết số tối thiểu được viết trên một số quân bài còn lại trong bộ bài, nhưng không biết quân bài này (hoặc các quân bài) nằm ở đâu trong bộ bài.
Nhiệm vụ của bạn là xác định tổng số lần Akaki nhìn vào lá bài trên cùng từ bộ bài.
Đầu vào
Dòng đầu tiên theo sau là số nguyên dương n (1 ≤ n ≤ 100 000) — số lượng quân bài trong bộ bài.
Dòng thứ hai chứa dãy n số nguyên dương a1, a2, ..., an ( 1 ≤ ai ≤ 100 000), trong đó ai bằng với số được viết trên thẻ trên cùng thứ i từ bộ bài.
Đầu ra
In tổng số lần Akaki nhìn vào quân bài trên cùng của bộ bài.
|
Nhập |
Đầu ra |
|
4
6 3 1 2
|
7 |
1
1000
|
1 |
7
3 3 3 3 3 3 3
|
7 |
Lưu ý
Trong ví dụ đầu tiên, Akaki trước tiên sẽ nhìn vào quân bài có số 6, đặt nó ở dưới cùng của bộ bài, sau đó là quân bài có số 3, cũng đặt nó ở dưới cùng của bộ bài, và sau đó là quân bài có số số 1. Anh ta sẽ đặt quân bài có số 1 sang một bên, vì nó chứa số ít nhất còn lại trong bộ bài. Sau đó, các quân bài trong bộ bài sẽ nằm theo thứ tự [2, 6, 3] từ trên xuống dưới. Sau đó, Akaki sẽ nhìn vào lá bài trên cùng có số 2 và đặt nó sang một bên. Sau đó, các quân bài trong bộ bài sẽ nằm theo thứ tự [6, 3] từ trên xuống dưới. Sau đó, Akaki sẽ nhìn vào quân bài có số 6, đặt nó ở dưới cùng của bộ bài, và sau đó là quân bài có số 3, anh ấy sẽ đặt nó sang một bên. Sau đó, một lá bài có số 6 sẽ vẫn còn trong bộ bài, Akaki sẽ xem xét và đặt sang một bên. Như vậy, Akaki sẽ xem xét 7 lá bài.
(c) Kurbatov E., 2018