English · Original
Chinese · Translation
Formal · Original
Vasily has a deck of cards consisting of _n_ cards. There is an integer on each of the cards, this integer is between 1 and 100 000, inclusive. It is possible that some cards have the same integers on them.
Vasily decided to sort the cards. To do this, he repeatedly takes the top card from the deck, and if the number on it equals the minimum number written on the cards in the deck, then he places the card away. Otherwise, he puts it under the deck and takes the next card from the top, and so on. The process ends as soon as there are no cards in the deck. You can assume that Vasily always knows the minimum number written on some card in the remaining deck, but doesn't know where this card (or these cards) is.
You are to determine the total number of times Vasily takes the top card from the deck.
## Input
The first line contains single integer _n_ (1 ≤ _n_ ≤ 100 000) — the number of cards in the deck.
The second line contains a sequence of _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 100 000), where _a__i_ is the number written on the _i_\-th from top card in the deck.
## Output
Print the total number of times Vasily takes the top card from the deck.
[samples]
## Note
In the first example Vasily at first looks at the card with number 6 on it, puts it under the deck, then on the card with number 3, puts it under the deck, and then on the card with number 1. He places away the card with 1, because the number written on it is the minimum among the remaining cards. After that the cards from top to bottom are \[2, 6, 3\]. Then Vasily looks at the top card with number 2 and puts it away. After that the cards from top to bottom are \[6, 3\]. Then Vasily looks at card 6, puts it under the deck, then at card 3 and puts it away. Then there is only one card with number 6 on it, and Vasily looks at it and puts it away. Thus, in total Vasily looks at 7 cards.
Vasily 有一副由 #cf_span[n] 张牌组成的牌堆。每张牌上有一个整数，该整数介于 #cf_span[1] 和 #cf_span[100 000] 之间（包含两端）。可能存在多张牌具有相同的整数。
Vasily 决定对这些牌进行排序。为此，他反复从牌堆顶部取一张牌，如果这张牌上的数字等于当前牌堆中所有牌的最小值，则将这张牌移出牌堆；否则，他将这张牌放到牌堆底部，然后从顶部取下一张牌，依此类推。当牌堆为空时，该过程结束。你可以假设 Vasily 总是知道剩余牌堆中某个牌上的最小值，但他不知道这个最小值的牌（或这些牌）具体在哪里。
你需要确定 Vasily 从牌堆顶部取牌的总次数。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 牌堆中的牌数。
第二行包含一个由 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] 组成的序列 (#cf_span[1 ≤ ai ≤ 100 000])，其中 #cf_span[ai] 表示从顶部数第 #cf_span[i] 张牌上的数字。
请输出 Vasily 从牌堆顶部取牌的总次数。
在第一个例子中，Vasily 首先查看数字为 #cf_span[6] 的牌，将其放到牌堆底部；然后查看数字为 #cf_span[3] 的牌，也放到牌堆底部；接着查看数字为 #cf_span[1] 的牌，由于这是当前剩余牌中的最小值，他将这张牌移出牌堆。此时牌堆从上到下为 #cf_span[[2, 6, 3]]。接着 Vasily 查看顶部数字为 #cf_span[2] 的牌，并将其移出牌堆。此时牌堆从上到下为 #cf_span[[6, 3]]。然后 Vasily 查看牌 #cf_span[6]，将其放到牌堆底部；接着查看牌 #cf_span[3]，由于这是当前最小值，将其移出牌堆。此时只剩一张数字为 #cf_span[6] 的牌，Vasily 查看它并将其移出牌堆。因此，Vasily 总共查看了 #cf_span[7] 张牌。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 牌堆中的牌数。
第二行包含一个由 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] 组成的序列 (#cf_span[1 ≤ ai ≤ 100 000])，其中 #cf_span[ai] 表示从顶部数第 #cf_span[i] 张牌上的数字。
## Output
请输出 Vasily 从牌堆顶部取牌的总次数。
[samples]
## Note
在第一个例子中，Vasily 首先查看数字为 #cf_span[6] 的牌，将其放到牌堆底部；然后查看数字为 #cf_span[3] 的牌，也放到牌堆底部；接着查看数字为 #cf_span[1] 的牌，由于这是当前剩余牌中的最小值，他将这张牌移出牌堆。此时牌堆从上到下为 #cf_span[[2, 6, 3]]。接着 Vasily 查看顶部数字为 #cf_span[2] 的牌，并将其移出牌堆。此时牌堆从上到下为 #cf_span[[6, 3]]。然后 Vasily 查看牌 #cf_span[6]，将其放到牌堆底部；接着查看牌 #cf_span[3]，由于这是当前最小值，将其移出牌堆。此时只剩一张数字为 #cf_span[6] 的牌，Vasily 查看它并将其移出牌堆。因此，Vasily 总共查看了 #cf_span[7] 张牌。
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of cards.
Let $ A = (a_1, a_2, \dots, a_n) $ be the sequence of integers on the cards, where $ a_i $ is the number on the $ i $-th card from the top.
Let $ \min(S) $ denote the minimum value in a multiset $ S \subseteq \{a_1, \dots, a_n\} $.
**Constraints**
1. $ 1 \leq n \leq 100{,}000 $
2. $ 1 \leq a_i \leq 100{,}000 $ for all $ i \in \{1, \dots, n\} $
**Process**
Vasily performs the following repeatedly until the deck is empty:
- Take the top card.
- If its value equals the current minimum value in the deck, remove it.
- Otherwise, move it to the bottom of the deck.
**Objective**
Compute the total number of times a card is taken from the top of the deck during this process.
API Response (JSON)
{
"problem": {
"name": "B. Cards Sorting",
"description": {
"content": "Vasily has a deck of cards consisting of _n_ cards. There is an integer on each of the cards, this integer is between 1 and 100 000, inclusive. It is possible that some cards have the same integers on",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF830B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Vasily has a deck of cards consisting of _n_ cards. There is an integer on each of the cards, this integer is between 1 and 100 000, inclusive. It is possible that some cards have the same integers on...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Vasily 有一副由 #cf_span[n] 张牌组成的牌堆。每张牌上有一个整数，该整数介于 #cf_span[1] 和 #cf_span[100 000] 之间（包含两端）。可能存在多张牌具有相同的整数。\n\nVasily 决定对这些牌进行排序。为此，他反复从牌堆顶部取一张牌，如果这张牌上的数字等于当前牌堆中所有牌的最小值，则将这张牌移出牌堆；否则，他将这张牌放到牌堆底部，然后从顶部取下一张牌，...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the number of cards. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of integers on the cards, where $ a_i $ is the number on the $ i $-th card from ...",
"is_translate": false,
"language": "Formal"
}
]
}