At first if n is odd the answer is 0, because the perimeter of any rectangle is even number always.
If n is even than the number of the rectangles which can be constructed equals to n / 4. If n is divisible by 4 than we will count the square which is deprecated, so in this case we need to subtract 1 from the answer.
Asymptotic behavior — O(1).
Для начала найдем минимум в заданном массиве, обозначим его переменной minimum. Понятно, что всегда возможно покрасить n * minimum клеток. Тогда понятно, что нужно найти такой минимум в массиве, перед которым слева стоит как можно больше чисел, больших чем минимум. Другими словами, нужно найти два минимума, расстояние между которыми наибольшее, с учетом цикличности. Если же минимум в массиве один, то понятно, что начинать красить нужно с цвета, который находится сразу после него (опять же с учетом цикличности). Это можно сделать за один проход по массиву, поддерживая в отдельной переменной позицию ближайшего слева минимума. Если текущее число равно минимуму, тогда нужно обновить эту переменную и ответ.
Асимтотика такого решения — O(n), где n — количество различных цветов.
