Minimum Colors to Paint Buildings

Given \(n\) buildings with heights \(h_1, h_2, \dots, h_n\), the task is to determine the minimum number of colors needed to paint these buildings such that no two adjacent buildings with different heights are painted with the same color in a conflicting manner. In simple terms, if there exists any adjacent pair \(h_i \neq h_{i+1}\), then at least two colors are required. Otherwise, if all buildings have the same height, only one color is sufficient. Additionally, when there is only one building, the answer is trivially 1.

The optimal strategy is to check if all buildings have the same height. If not, the answer is 2; otherwise, it is 1.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the number of buildings. The second line contains \(n\) space-separated integers, where each integer represents the height of a building.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of colors required to paint the buildings under the given constraints.

1
4

1