시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 60 | 30 | 28 | 51.852% |
Noah suggests the following card game: You are given a deck of cards, each with a distinct positive integer value written on it. The cards are shuffled and placed in a row. Your objective is to arrange the cards in the row so that the values are monotonically increasing initially, and then monotonically decreasing for the remainder of the sequence.
The only move that is allowed is that two neighboring cards may swap positions. Cards may only swap positions if they are adjacent to each other.
Note that in the final ordered sequence, the initial increasing portion of the sequence may be empty (such that the whole sequence is in descending order). Likewise it is allowed for the decreasing portion of the sequence to be empty.
What is the fewest number of moves needed to get the cards arranged in the proper order?
The first line of input contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$), which is the number of cards.
Each of the next $n$ lines contains a single integer $c$ ($1 \le c \le 10^9$). These are the cards, in their initial order. They will all be distinct.
Output a single integer, which is the fewest number of moves needed to arrange the cards as specified.
8 7 4 8 10 1 2 6 9
7
ICPC > Regionals > North America > Southeast USA Regional > 2020 Southeast USA Regional Programming Contest C번
ICPC > Regionals > North America > Mid-Central Regional > 2020 Mid-Central Regional Programming Contest N번
ICPC > Regionals > North America > Pacific Northwest Regional > 2020 ICPC Pacific Northwest Region > Division 1 E번
ICPC > Regionals > North America > Pacific Northwest Regional > 2020 ICPC Pacific Northwest Region > Division 2 V번
ICPC > Regionals > North America > Mid-Atlantic Regional > 2020 Mid-Atlantic USA Regional Contest I번
ICPC > Regionals > North America > South Central USA Regional > 2020 South Central USA Regional Contest C번