Maximizing Sticker Value

You are given a sequence of stickers with positive integer values arranged in a line. Your task is to determine the maximum possible sum of sticker values you can pick such that no two selected stickers are adjacent. Formally, if the sticker values are given by \(a_1, a_2, \ldots, a_n\), you need to choose a subset of indices \(\{i_1, i_2, \dots, i_k\}\) satisfying \(i_{j+1} - i_j \geq 2\) for all valid \(j\), and maximize the sum \(\sum_{j=1}^{k} a_{i_j}\).

This problem is a variant of the classical House Robber problem and can be solved efficiently using dynamic programming.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)) which represents the number of stickers.
• The second line contains \(n\) space-separated integers, each representing the value of a sticker.

outputFormat

Output a single integer, which is the maximum sum of the sticker values that can be collected without selecting any two adjacent stickers.

1
5

5