The Problem In Discussion is : https://codeforces.net/contest/1839/problem/D

Observations:
- The solution will be decreasing.
- Say you place some zeroes then each zero removes some contiguous subarray, the 0 is present in this subarray and subarrays of two zeroes don't overlap.
- A subarray that zero removes, give cost equal to the number of elements in the subarray.
- Now it is equivalent that each zero is present in the starting of the subarray that it is removing.
- So this can be solved with dp.
- This problem is very identical to LIS.
- In fact answer for the last query is always n — size_of_lis of the array.

State of dp
dp[i][k][2]:
1. dp[i][k][0] -> minimum no of removed elements upto index i such that you have used k zeros and i'th element is not removed.
2. dp[i][k][1] -> minimum no of removed elements upto index i such that you have used k zeroes and i'th element is removed.
'
Transitions:
1. If we are removing the i'th element, and we have used k zeroes, then, we are talking about dp[i][k][1], the transition would be :
— that we removed the (i-1)th element and we did it in k zeroes so we can continue the removal so dp[i][k][1] be dp[i-1][k][1] + 1 (as we removed the i'th element)
— that we didn't remove the (i-1)th element, so we have to place a zero just before the i'th element so we can remove it. So dp[i][k][1] = dp[i-1][k-1][0] + 1 .