Maximum Candies with At Most Two Types in a Line

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Problem

Given a line of candies represented by a 1D sequence candies, where each position has a candy type.

You may pick at most two distinct candy types, and the candies you pick must come from a contiguous segment: starting at some index and moving right, picking adjacent candies one by one.

Rule: once you are about to encounter a third distinct candy type, you must stop immediately (you cannot pick that candy or anything to its right).

Return the maximum number of candies you can pick under these rules (i.e., the length of the longest contiguous segment containing at most two distinct types).

Examples

Input: [1,2,1] Output: 3

Input: [1,2,3,2,2] Output: 4

Constraints (typical)

1 <= n <= 2*10^5

Candy types are integers

Expected: O(n) time

Example

Input

3

1 2 1

Output

3

Complete solveMaximumCandiesTwoTypesLine. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.