What do we need? We need to get the non-decreasing array. Then, let's use the given operation on each element x, such that element before x is bigger than x. In other words, let's use the operation on index i, if a[i — 1] > a[i]. We can easily keep the difference between any two adjacent elements after index i by using the operation on suffix(a[i], a[i + 1], ..., a[n — 1]). It works, because each element on suffix will increase by equal value. To skip the part with addition on suffix(it's too slow to do it), let's solve the problem from right to left.

90106658