Maximum Sum of Non-Adjacent Buildings

You are given n buildings in a row, each with a certain height. Your task is to select a subset of these buildings such that no two selected buildings are adjacent, and the sum of the heights of the selected buildings is maximized.

Let \( h_1, h_2, \dots, h_n \) denote the heights of the buildings. You need to choose a subset \( S \subseteq \{1, 2, \dots, n\} \) with the constraint that if \( i \in S \), then \( i+1 \notin S \). The goal is to maximize \( \sum_{i \in S} h_i \).

Example:

Input: 4
       1 2 3 1
Output: 4

inputFormat

The first line contains a single integer n (the number of buildings). The second line contains n space-separated integers representing the heights of the buildings.

outputFormat

Output a single integer, the maximum sum of heights from the selected non-adjacent buildings.

## sample

4
1 2 3 1

4

</p>