What you need to do is to find longest increasing subsequence. If its length is K and length of array is N then the answer is N - K.

Dynamic programming: dp[i] = the longest increasing subsequence ending in i-th element.

So dp[i] = {maximum for all j: 0 <= j < i and a[j] < a[i]} (dp[j] + 1)

So basically

int dp[N];
for (int i = 0; i < N; i++) {
   dp[i] = 1;
   for (int j = 0; j < i; j++) {
      if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
   }
}
int res = 0;
for (int i = 0; i < N; i++) res = max(res, dp[i]);

We can improve solution to O(NlogM), where M = length of LIS. Here it was discussed.

My code in C++