G - Sort from 1 to 4 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 625 点

問題文

全ての要素が 1 以上 4 以下の整数である、長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

高橋君は次の操作を何回でも (0 回でも良い) 繰り返し行う事ができます。

  • 1\leq i<j\leq N をみたす整数の組 (i,j) を選び、A_i と A_j を交換する。

数列 A を広義単調増加にするために必要な操作回数の最小値を求めてください。
ただし、数列 A が広義単調増加であるとは、1\leq i\leq N-1 をみたすすべての整数について A_i\leq A_{i+1} が成り立つことをさします。

制約

  • 2 \leq N \leq 2\times 10^5
  • 1\leq A_i \leq 4
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N

出力

数列 A を広義単調増加にするために必要な操作回数の最小値を一行に出力せよ。

入力例 1

6
3 4 1 1 2 4

出力例 1

3

次のようにして 3 回の操作で A を広義単調増加にすることができます。

  • (i,j)=(2,3) を選び、A_2 と A_3 を交換する。A=(3,1,4,1,2,4) となる。
  • (i,j)=(1,4) を選び、A_1 と A_4 を交換する。A=(1,1,4,3,2,4) となる。
  • (i,j)=(3,5) を選び、A_3 と A_5 を交換する。A=(1,1,2,3,4,4) となる。

2 回以下の操作で A を広義単調増加にすることはできないため、このとき操作回数が最小となります。
よって、3 を出力します。

入力例 2

4
2 3 4 1

出力例 2

3

Score : 625 points

Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N, consisting of integers between 1 and 4.

Takahashi may perform the following operation any number of times (possibly zero):

  • choose a pair of integer (i,j) such that 1\leq i<j\leq N, and swap A_i and A_j.

Find the minimum number of operations required to make A non-decreasing.
A sequence is said to be non-decreasing if and only if A_i\leq A_{i+1} for all 1\leq i\leq N-1.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • 1\leq A_i \leq 4
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the minimum number of operations required to make A non-decreasing in a single line.

Sample Input 1

6
3 4 1 1 2 4

Sample Output 1

3

One can make A non-decreasing with the following three operations:

  • Choose (i,j)=(2,3) to swap A_2 and A_3, making A=(3,1,4,1,2,4).
  • Choose (i,j)=(1,4) to swap A_1 and A_4, making A=(1,1,4,3,2,4).
  • Choose (i,j)=(3,5) to swap A_3 and A_5, making A=(1,1,2,3,4,4).

This is the minimum number of operations because it is impossible to make A non-decreasing with two or fewer operations.
Thus, 3 should be printed.

Sample Input 2

4
2 3 4 1

Sample Output 2

3