[Medium] ConvexSequence

주어진 수열 a[0..n-1]에 연산을 적절히 수행해서 만든 convex sequence 를 x[0..n-1] 라고 하자. x[i] <= a[i] x[i] <= (x[i-1] + x[i+1]) / 2 가 성립한다. 연립하면 x[i] <= (a[i-1] + a[i+1]) / 2 다. x[i] 의 upper bound 를 min( a[i], (a[i-1] + a[i+1]) / 2 ) 라고 할 수 있다. 만약 (a[i-1] + a[i+1]) / 2 가 a[i]보다 더 작다면 이 값을 a[i]로 update해도 무방하다. a[i]가 줄어들면 이를 통해 x[i-1]과 x[i+1]의 upper bound 도 update 될 여지가 생긴다. 모든 위치에서 update가 일어나지 않을 때 까지 이 연산을 계속 반복하고 나면 그것이 답이 된다. 연산을 어떤 순서로 적용하냐는 중요하지 않다. 위의 부등식은 '반드시' 성립해야하는 조건이기 때문에 어떤 순서로 수행되든 무조건 수행되어야 하고, 같은 결과로 수렴하게 된다. 그럼 연산 수행횟수의 상한이 적다는 것을 증명할 수 있는가... 가 문제인데 이건 에디토리얼에 제대로 나와있지 않다. 최악의 데이터를 만들어 넣어봐도 4000번 미만이라고 하긴 하는데, 맘에 안듦. 에디토리얼에서는 이분탐색을 이용한 다른 알고리즘을 제시한 뒤, 그것의 수행횟수의 상한을 증명하고 있긴 하다.