<p>You are given an integer array, <code>nums</code>, and an integer <code>k</code>. <code>nums</code> comprises of only <code>0</code>&#39;s and <code>1</code>&#39;s. In one move, you can choose two <strong>adjacent</strong> indices and swap their values.</p>

<p>Return <em>the <strong>minimum</strong> number of moves required so that </em><code>nums</code><em> has </em><code>k</code><em> <strong>consecutive</strong> </em><code>1</code><em>&#39;s</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,0,0,1,0,1], k = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong> In 1 move, nums could be [1,0,0,0,<u>1</u>,<u>1</u>] and have 2 consecutive 1&#39;s.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,0,0,0,0,0,1,1], k = 3
<strong>Output:</strong> 5
<strong>Explanation:</strong> In 5 moves, the leftmost 1 can be shifted right until nums = [0,0,0,0,0,<u>1</u>,<u>1</u>,<u>1</u>].
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,0,1], k = 2
<strong>Output:</strong> 0
<strong>Explanation:</strong> nums already has 2 consecutive 1&#39;s.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>nums[i]</code> is <code>0</code> or <code>1</code>.</li>
	<li><code>1 &lt;= k &lt;= sum(nums)</code></li>
</ul>

class Solution {
public:
    int minMoves(vector<int>& nums, int k) {
      int n=nums.size();
      // left side (k-1)/2

      vector<long long>pref(n+1,1e15);
        deque<int>ones;
        long long sum=0;
      for(long long i=0;i<n;i++){
        if(nums[i]){
            ones.push_back(i);
            sum+=i;
            if(ones.size()>(k+1)/2){
                sum-=ones.front();
                ones.pop_front();
            }
           
        }
        
        if(ones.size()==(k+1)/2){
             
                long long elements=(k+1)/2;
                long long add=i*(i+1)/2-(i-elements)*(i-elements+1)/2;
                long long minus=sum;
                add-=minus;
               
                pref[i]=add;
            }
        
      }
      int rem=k-(k+1)/2;
      ones.clear();
    sum=0;
    vector<long long>suff(n,1e15);
     for(long long i=n-1;i>=0;i--){
       
        if(ones.size()==rem){
             
                long long elements=rem;
                long long add=-((i+elements)*(i+elements+1)/2-(i)*(i+1)/2)+sum;
                //cout<<sum<<" "<<elements<<endl;
                suff[i]=add;
            }
        
         if(nums[i]){
            ones.push_back(i);
            sum+=i;
            if(ones.size()>rem){
                sum-=ones.front();
                ones.pop_front();
            }
           
        }
      }
    long long ans=1e15;
   
      for(int i=0;i<n;i++){
        ans=min(ans,pref[i]+suff[i]);
      }
      return ans;
    }
};
153000