Zigzag

A sequence of numbers $x(1), x(2), \ldots, x(k)$ is zigzag if no three of its consecutive elements form a nonincreasing or nondecreasing sequence. More precisely, for all $i = 1, 2, \ldots, k-2$, either $x(i+1) < x(i)$ and $x(i+1) < x(i+2)$, or $x(i+1) > x(i)$ and $x(i+1) > x(i+2)$.

You are given two sequences $a(1), \ldots, a(n)$ and $b(1), \ldots, b(m)$. Remove elements from both sequences so that they become equal and the remaining sequence is zigzag. If the minimum number of removed elements is $k$, the answer is $m+n-k$. Find the length of the longest common zigzag subsequence.

The first line contains $n$ ($1\leq n \leq 2000$), followed by $n$ integers $a(1), \ldots, a(n)$. The second line contains $m$ ($1 \leq m \leq 2000$), followed by $m$ integers $b(1), \ldots, b(m)$. Every $a(i)$ and $b(i)$ is in the range $[-10^9, 10^9]$.

Print one line containing the length of the longest common zigzag subsequence of $a$ and $b$.