Coloring the Array for Maximum Score

You are given an array \(A\) of \(n\) positive integers arranged from left to right. Your task is to color each element of \(A\) either red or blue, and then compute a score as follows.

Define an integer array \(C\) of length \(n\). For each \(1 \le i \le n\):

• If there is no element to the left of \(A_i\) that is colored with the same color as \(A_i\), then \(C_i = 0\).
• Otherwise, let \(A_j\) be the closest element to the left of \(A_i\) having the same color. If \(A_i = A_j\), then \(C_i = A_i\); otherwise, \(C_i = 0\).

Your final score is the sum \(\sum_{i=1}^n C_i\). Determine the maximum score you can obtain by an appropriate coloring strategy.

Note: If an element does not have a previous element in the same color, it contributes zero to the final score. Your goal is to choose a valid red/blue assignment for each element to maximize the overall score.

inputFormat

The first line contains a single integer \(n\) representing the number of elements in the array \(A\).
The second line contains \(n\) space-separated positive integers \(A_1, A_2, \ldots, A_n\).

outputFormat

Output a single integer --- the maximum final score that can be achieved.

sample

3
1 2 1

1