For each element of the array, calculate what would its position be if we sort the array (let pos[i] be the position of element i in a sorted array). Then, find the maximum value x such that all the elements which have pos <= x are sorted (for example, let the array be [3, 4, 1, 2, 5]. Maximum x = 2 because 1 and 2 are sorted (2 is behind 1), but 3 is before 1 and 2 (so 1, 2 and 3 are not sorted)). In the end you just put all the other elements to the end of the array (in the correct order, of course). So, minimum number of operations is N (number of elements in the array) — x.

solve(vector<int>arr){
int st=0;
vector<int>v;
v=arr;
int ans=0;
int n=v.size();
sort(v.begin(),v.end());
for(int i=0;i<n;i++){
int req=v[i];
while(st<n && arr[st]!=req){
st++;
ans++;
}
st++;
if(st>=n){
break;
}
}
return ans;
}

I had made this question for a round on CodeChef. Here is the editorial.