Given an array A with n integers. In one turn one can apply the following operation to any consecutive subarray A[l..r] : assign to all A i (l <= i <= r) median of subarray A[l..r] . Let max be the maximum integer of A . We want to know the minimum number of operations needed to change A to an array of n integers each with value max. For example, let A = [1, 2, 3] . We want to change it to [3, 3, 3] . We can do this in two operations, first for subarray A[2..3] (after that A equals to [1, 3, 3] ), then operation to A[1..3] . Also,median is defined for some array A as follows. Let B be the same array A , but sorted in non-decreasing order. Median of A is B m (1-based indexing), where m equals to (n div 2)+1 . Here 'div' is an integer division operation. So, for a sorted array with 5 elements, median is the 3rd element and for a sorted array with 6 elements, it is the 4th element.
Since the maximum value of N is 30.I thought of brute forcing the result could there be a better solution.