Maximum Sum Subarray with Two Distinct Integers

You are given an array of n integers. Your task is to find the contiguous subarray that has at most two distinct integers and yields the maximum sum.

Formally, given an integer \( n \) and an array \( a \) of length \( n \), determine the subarray \( a[l..r] \) (with \( 0 \leq l \leq r < n \)) such that there are at most two distinct integers in \( a[l..r] \) and the sum \( \sum_{i=l}^{r} a_i \) is maximized.

Note: A subarray is defined as a contiguous segment of the array.

inputFormat

The input is given via stdin:

• The first line contains an integer \( n \), representing the number of elements in the array.
• The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Output the maximum sum of any contiguous subarray that contains at most two distinct integers. The output should be printed to stdout.

5
1 2 1 2 3

6