题目描述

2048 年，小 F 乘坐载人飞船探索太空，沿途观测到 $n$ 颗恒星，依次编号为 $1$ 到 $n$。小 F 记录下每颗恒星拥有的行星数量，形成一个非负整数序列 $S$，其中 $s_i$ 表示编号为 $i$ 的恒星拥有的行星数量。

• 若 $s_i$ 为偶数，称该恒星为偶恒星；
• 若 $s_i$ 为奇数，称该恒星为奇恒星。

小 F 想找到一个连续子区间，使其中奇恒星与偶恒星的数量相等，并计算该区间中行星数量不同的恒星数量的最大值。

输入格式

• 第一行包含整数 $n$ $(1 \le n \le 2000)$，表示恒星数量。
• 第二行包含 $n$ 个非负整数 $s_1, s_2, \dots, s_n$ $(1 \le s_i \le 10^5)$，表示每颗恒星的行星数量。

输出格式

包含一个整数 —— 满足条件的连续区间中最多有多少颗行星数量不同的恒星。

样例输入 1

4
2 5 4 3

样例输出 1

4

样例解释 1

区间 [2,5,4,3] 中，偶恒星为 2,4，奇恒星为 5,3，奇偶各两颗，且行星数量互不相同，共 $4$ 颗。

样例输入 2

5
3 4 4 5 6

样例输出 2

4

样例解释 2

区间 [3,4,4,5,6] 中，奇恒星为 3,5，偶恒星为 4,6。行星数量不同的恒星有 3,4,5,6，共 $4$ 颗。

数据范围

特殊性质 A：所有 $s_i$ 互不相同。