Max Sum without Consecutive Difficulties

You are given a series of tasks, each with a difficulty level. Your goal is to select a subset of these tasks such that no two selected tasks are consecutive, thereby maximizing the sum of the difficulties of the selected tasks.

Formally, let the difficulty of tasks be given by an array \(a_1, a_2, \dots, a_n\). You need to compute the maximum sum \(S\) such that if you select task \(i\), you cannot select task \(i+1\). This can be formulated using dynamic programming as follows:

\[ \text{dp}[0] = a_1, \quad \text{dp}[1] = \max(a_1, a_2), \] \[ \text{dp}[i] = \max(\text{dp}[i-1], \text{dp}[i-2] + a_{i+1}) \quad \text{for } i \ge 2. \]

Input is provided via standard input and the output must be printed to standard output.

inputFormat

The first line contains an integer (n) — the number of tasks. The second line contains (n) space-separated integers representing the difficulty levels of the tasks.

outputFormat

Output a single integer denoting the maximum sum achievable by selecting non-adjacent tasks.## sample

6
3 5 1 9 2 8

22

</p>