在中国，每逢喜庆节日，人们都会舞龙，从春节开始舞龙，然后二月“龙抬头”、端午节时也舞龙。舞龙时，龙跟着绣球做各种动作，穿插，不断地展示扭、挥、仰、跪、跳、摇等多种姿势。

有 n 名表演者排成一排表演舞龙，表演者将杆举低用 1 表示，杆举高的表演者用 2 表示。这样，所有表演者的动作可以由序列 a[1], a[2], ..., a[n] 表示。

现在你希望让舞龙表演更好看些。你选择一个区间 [l, r] (1≤l≤r≤n)，然后将 a[l], a[l + 1], ..., a[r] 翻转，使得新序列的最长不下降子序列的长度尽可能大。

不下降子序列指下标为 p[1], p[2], ..., p[k] 且满足 1≤p[1]<p[2]<...<p[k]≤n, a[p[1]] ≤ a[p[2]] ≤ ... ≤ a[p[k]] 的序列。该子序列的长度为 k。

第一行包含一个整数 n(1≤ n≤2000)，表示原始序列的长度。

第二行包含 n 个空格分隔的整数，表示原始序列 a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 2, i = 1, 2, ..., n)。

输出一个整数，表示新序列的最长不下降子序列的最大可能长度。

10
1 1 2 2 2 1 1 2 2 1

9

在样例中，将区间 [3, 7] 翻转后，数组将变为 [1, 1, 1, 1, 2, 2, 2, 2, 2, 1] ，其中最长非递减子序列的长度为 9。