Can someone please explain the solution to this problem?
http://usaco.org/index.php?page=viewproblem2&cpid=1162.
I have tried solving the problem. What I thought is that we can iterate from 1 to n, and for each A[I[, if it is less than A[i-1] and if there is no element in between yet, then we can increment the answer for the range (A[I-1], A[i]-1) by 1. However, I figured out, that’s the wrong approach. From there, i could not think further. I also tried reading the solution mentioned here.http://usaco.org/current/data/sol_prob2_gold_dec21.html
however, I was not able to understand it. It would be helpful if someone could make me get through it in some simple words and details of each step.
Also, if you are mentioning any other solution, please care to provide proof of it.
Thank you in advance.