title: Number of possible arrays such that adjacent elements have difference atmost 1
body: <p>You know that an array has n integers between 1 and m, and the difference between two adjacent values is at most 1.</p>
  
  <p>Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.</p>
  
  <p>The unknown values will be given as "0" in the input array.
  Give the number of arrays modulo 1e9+7</p>
  
  <p>The problem could be broken into two parts. One is where the unknown is in between the knowns, then it's simple to calculate the number of arrays,
  The difference can only be 0,1 or 2. it can't be 3, because eg 2 0 5, then there is No value that gives the correct array. The input will always have a difference between the unknown as possible values. if the difference is 0, 2 0 2, then 3 values are possible, if the difference is 1, 2 0 3, then 1 and 3 are the only possible values, so 2 values possible. for the difference of 2, there is only 1 value so no change in the result is ok.</p>
  
  <p>But the second case where the unknowns are in between unknowns is what troubles me.</p>
  
  <pre><code>#include &lt;bits/stdc++.h&gt;
  
  using namespace std;
  
  const int MOD   = 1e9 + 7;
  
  
  int main() {
  
      int n,m;cin&gt;&gt;n&gt;&gt;m;
      vector&lt;int&gt; arr(n);
  
      for(int i=0;i&lt;n;i++) cin&gt;&gt;arr[i];
  
      int res=1;
  
      if(arr[0]==0 &amp;&amp; arr[1]!=0)
          res=(res%MOD*3)%MOD;
      if(arr[n-1]==0 &amp;&amp; arr[n-2]!=0)
          res=(res%MOD*3)%MOD;
  
      //for unknowns between knowns
      for(int i=1;i&lt;n-1;i++)
      {
          if(arr[i]==0 &amp;&amp; arr[i-1]!=0 &amp;&amp; arr[i+1]!=0)
          {
              int val=arr[i+1]-arr[i-1];
              if(val==0)
                  res=(res%MOD*3)%MOD;
              else if(val==1)
                  res=(res%MOD*2)%MOD;
          }
      }
  
      //for unknows between unknowns(I don't know how to approach this. Brute force will surely give TLE)
      for(int i=0;i&lt;n;i++)
      {
          int st=i;
          while(i&lt;n &amp;&amp; arr[i]==0)
              i++;
  
          if(arr[i]!=0) i--;
  
          if(i-st&gt;=1)
          {
              if(st!=0 &amp;&amp; i!=n-1)
              {
  
              }
          }
  
      }
  
  
      cout&lt;&lt;res;
  
  
      return 0;
  }
  </code></pre>
  
  <p>for 2 0 2, output is 3 ([2 1 2][2 2 2][2 3 2])</p>
  
  <p>I want to know how to solve the 2nd case of this problem, with continuous unknown values.</p>