/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は、横一列に並んだ N 個の看板を管理しています。左から i 番目の看板には整数 A_i が書かれています。
高橋君は、看板に書かれた整数が左から順に広義単調増加となるように、いくつかの看板の整数を書き換えることにしました。
具体的には、書き換え後の看板の整数を左から順に A'_1, A'_2, \dots, A'_N としたとき、すべての 1 \le i \le N - 1 について以下の条件を満たすようにしたいです。
- A'_i \le A'_{i+1}
高橋君は 1 回の操作で、看板を 1 つ選び、そこに書かれた整数を任意の整数に書き換えることができます。
条件を満たすために必要な操作回数の最小値を求めてください。
制約
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
- 1 行目には、看板の個数を表す整数 N が与えられる。
- 2 行目には、N 個の看板に書かれた整数を表す A_1, A_2, \dots, A_N がスペース区切りで与えられる。
出力
条件を満たすために必要な操作回数の最小値を 1 行で出力せよ。
入力例 1
5 3 1 4 1 5
出力例 1
2
入力例 2
4 2 3 3 7
出力例 2
0
入力例 3
15 10 40 20 50 30 70 60 90 80 100 1000000000 500 800 999999999 1000000000
出力例 3
5
入力例 4
40 54 12 87 23 91 34 65 18 76 43 99 2 81 59 31 70 45 88 16 62 38 95 27 73 50 84 9 67 41 93 20 78 56 3 89 35 68 47 97 25
出力例 4
30
入力例 5
1 1000000000
出力例 5
0
Score : 433 pts
Problem Statement
Takahashi manages N signboards arranged in a horizontal row. The i-th signboard from the left has an integer A_i written on it.
Takahashi has decided to rewrite the integers on some of the signboards so that the integers written on the signboards are non-decreasing from left to right.
Specifically, letting the integers on the signboards after rewriting be A'_1, A'_2, \dots, A'_N from left to right, he wants to satisfy the following condition for all 1 \le i \le N - 1:
- A'_i \le A'_{i+1}
In one operation, Takahashi can choose one signboard and rewrite the integer written on it to any integer.
Find the minimum number of operations required to satisfy the condition.
Constraints
- 1 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
- The first line contains an integer N, representing the number of signboards.
- The second line contains A_1, A_2, \dots, A_N separated by spaces, representing the integers written on the N signboards.
Output
Print the minimum number of operations required to satisfy the condition in a single line.
Sample Input 1
5 3 1 4 1 5
Sample Output 1
2
Sample Input 2
4 2 3 3 7
Sample Output 2
0
Sample Input 3
15 10 40 20 50 30 70 60 90 80 100 1000000000 500 800 999999999 1000000000
Sample Output 3
5
Sample Input 4
40 54 12 87 23 91 34 65 18 76 43 99 2 81 59 31 70 45 88 16 62 38 95 27 73 50 84 9 67 41 93 20 78 56 3 89 35 68 47 97 25
Sample Output 4
30
Sample Input 5
1 1000000000
Sample Output 5
0