Statement

Andrea spends a lot of time at the gym and thinks that good music can improve his performance. He has therefore compiled a playlist of N songs that he will listen to in order, assigning each one a catchiness rating C_i. However, he realizes that switching from a more catchy song to a less catchy one could impact his performance during training. In particular, Andrea calculates how unbalanced the playlist is by adding up all the decreases in catchiness between adjacent pairs of songs. Formally, the imbalance U = \sum_i = 1^N - 1max{0, C_i - 1 - C_i}. To improve the playlist, he can choose a single song and move it to any position within the playlist (or leave it where it was). What is the minimum imbalance U that can be achieved by performing the above operation?