title: Minimum no of changes required to make array strictly increasing
body: <p>I have a problem in which we have an array of positive numbers and we have to make it strictly increasing by making zero or more changes to the array elements.</p>
  <p>We are asked the minimum number of changes required to make the array strictly increasing.</p>
  <p><strong>Example</strong></p>
  <p>if array is 1 2 9 10 3 15</p>
  <p>so ans=1 if change 3 to some number between 12 to 14.</p>
  <p>if 1 2 2 2 3 4 5</p>
  <p>ans=5</p>
  <p>since changing 2 to 3 then 2 to 4 then 3 to 5 then 4 to 6 then 5 to 7</p>
  <p><strong>Constraints:</strong></p>
  <p>Number of elements in array &lt;= 10^6</p>
  <p>Each element &lt;= 10^9</p>
  <p>Can somebody give me an algorithm?</p>
  <p>Link to the detailed problem with sample test cases
  <a href="https://www.hackerearth.com/problem/algorithm/find-path/" rel="nofollow noreferrer">https://www.hackerearth.com/problem/algorithm/find-path/</a></p>
  <p>Since it is mini/max problem, it sounds like dynamic programming to me, but I'm not sure.</p>