If the given n is odd the answer is 0, because the perimeter of any rectangle is always even number.
If n is even the number of rectangles which can be construct equals to n / 4. If n is divisible by 4 we will count the square, which are deprecated, because we need to subtract 1 from the answer.
Asymptotic behavior — O(1).
At first let's find the minimum in the given array and store it in the variable minimum. It is easy to understand, that we always can paint n * minimum squres. So we need to find such a minimum in the array before which staying the most number of elements, which more than the minimum. In the other words we need to find 2 minimums in the array which are farthest from each other (do not forget about cyclical of the array). If there is only one minumum we need to start paint from the color which stay in the array exactly after the minimum (do not forget about cyclical of the array too). It can be done with help of iterations from the left to the right. We need to store the position of the nearest minimum in the variable and update her and the answer when we meet the element which equals to minimum.
Asymptotic behavior — O(n), where n — the number of different colors.
