1次元 bit dp

int N, M, A[101010];
int cnt[20];
int dp[1 << 20];
int rui[20][101010];

int main() {
	cin >> N >> M; //数、種類の数
	rep(i, 0, N) {
		cin >> A[i]; //種類の順
		A[i]--;
		cnt[A[i]]++; //各種類の個数
		rui[A[i]][i] = 1; //種類、順番(累積和)
	}
	//累積和
	rep(a, 0, M) rep(i, 1, N) rui[a][i] += rui[a][i - 1];//種類、i番目

	rep(msk, 0, 1 << M) dp[msk] = inf; //1: 計算済み
	dp[0] = 0;

	rep(msk, 0, 1 << M) {
		int done = 0; //計算済みの種類の総個数

		rep(i, 0, M) if (msk & (1 << i)) done += cnt[i];

		rep(nxt, 0, M) if (!(msk & (1 << nxt))) {
			int tot = dp[msk]; //計算済みの種類の変更が必要な数
			
			//rep(i, done, done + cnt[nxt]) if (A[i] != nxt) tot++;
			int nxt_cnt = rui[nxt][done + cnt[nxt] - 1]; //種類(nxt)の最後の場所(累積和)

			//続きのスペースの場所にあるnxtの個数
			if (0 < done) nxt_cnt -= rui[nxt][done - 1]; //種類(nxt)の最初の場所を引く(累積和)

			tot += cnt[nxt] - nxt_cnt; //移動が必要なnxtの個数を足す

			chmin(dp[msk + (1 << nxt)], tot);
		}
	}

	cout << dp[(1 << M) - 1] << endl;
}