Longest Fluctuating Sequence

Little Qiang has a 3×n array. In each column you may choose one number from one of the three rows or choose nothing. The chosen sequence (of columns where a number is selected) must satisfy the following conditions:

• If a number from the first row is chosen, then it must be not less than the previous chosen number. In other words, if the chosen number is a and the previous chosen number is b, then $$a \ge b$$.
• If a number from the second row is chosen, then it must be not greater than the previous chosen number, i.e., $$a \le b$$.
• If a number from the third row is chosen, then for any contiguous segment of selections from the third row the sequence must be monotonic in the same direction. More precisely, suppose the consecutive selections from the third row form a segment. Then they must be either all non-decreasing or all non-increasing. Note that when switching from a different row to the third row, the monotonicity of the new segment is determined solely by the current element.

The task is to find a sequence (by choosing at most one number per column, in order) that satisfies the above conditions and has the maximum possible length.

inputFormat

The first line contains a single integer n (the number of columns).
The next three lines each contain n space-separated integers, representing the three rows of the array.

outputFormat

Output a single integer – the maximum length of a valid fluctuating sequence.

sample

3
1 2 3
3 2 1
2 2 2

3