Problem : 361 - 1B. IOI草

Problem Statistics

Solved Member: 23　　Submission: 114　　User Tried: 28

Statement:

你最近在家養了一種叫做IOI草的高貴植物。你將 N 株草種成一列，由左到右的草高度分別為 h₁, h₂, ..., h_N。

IOI草很需要陽光，你希望這些草不被比他們高的草擋住陽光。更詳細一點，對於第 i(2 ≤ i ≤ N) 株草，你希望滿足下面至少一個條件：

● 對所有 1 ≤ j ≤ i-1，滿足 h_j ≤ h_i
● 對所有 i+1 ≤ k ≤ N，滿足 h_k ≤ h_i

你每次能夠交換兩株相鄰草的位置，你想知道你至少要交換幾次才能滿足要求呢？

Input:Output:

第一行有一個整數 N，代表草的數量。
接下來 N 行，每行一個整數，依序代表由左到右每株草的高度 h_i。

限制：
3 ≤ N ≤ 300000
1 ≤ h_i ≤ 10⁹

Subtask 1：(10分)
N ≤ 8

Subtask 2：(20分)
N ≤ 20

Subtask 3：(15分)
N ≤ 5000

輸出一個數字，代表最少需要交換幾次才能滿足要求。

Sample Input:Sample Output:

SAMPLE A:
6
2
8
4
5
3
6

SAMPLE B:
5
4
4
2
4
4

SAMPLE C:
4
1
3
4
2

SAMPLE A:
3

SAMPLE B:
2

SAMPLE C:
0

HINT:

SAMPLE A圖文並茂攻略：

Source:

2013/2014 JOI 合宿 1模（日本IOI國手考）

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	500ms	262144kb
0-2	500ms	262144kb
0-3	500ms	262144kb
1-1	500ms	262144kb	10
1-2	500ms	262144kb
1-3	500ms	262144kb
1-4	500ms	262144kb
1-5	500ms	262144kb
1-6	500ms	262144kb
1-7	500ms	262144kb
1-8	500ms	262144kb
1-9	500ms	262144kb
1-10	500ms	262144kb
2-1	500ms	262144kb	20
2-2	500ms	262144kb
2-3	500ms	262144kb
2-4	500ms	262144kb
2-5	500ms	262144kb
2-6	500ms	262144kb
2-7	500ms	262144kb
2-8	500ms	262144kb
2-9	500ms	262144kb
2-10	500ms	262144kb
3-1	1000ms	262144kb	15
3-2	1000ms	262144kb
3-3	1000ms	262144kb
3-4	1000ms	262144kb
3-5	1000ms	262144kb
3-6	1000ms	262144kb
3-7	1000ms	262144kb
3-8	1000ms	262144kb
3-9	1000ms	262144kb
3-10	1000ms	262144kb
4-1	1000ms	262144kb	55
4-2	1000ms	262144kb
4-3	1000ms	262144kb
4-4	1000ms	262144kb
4-5	1000ms	262144kb
4-6	1000ms	262144kb
4-7	1000ms	262144kb
4-8	1000ms	262144kb
4-9	1000ms	262144kb
4-10	1000ms	262144kb