시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 16 MB 7 3 3 42.857%

문제

Johnny designs chips for chipcards. There are $n$ ports at the upper and bottom boundary of such a chip. The ports at the upper boundary are labelled from left-to-right by consecutive natural numbers $1, 2, \ldots, n$; the ports at the bottom boundary are also labelled from left-to-right with the same numbers, but in a possibly other order.  A pair of ports labelled with the same number is connected by a straight-line path; the paths are grouped into layers and the paths in one layer cannot cross.  Furthermore, ports at both boundaries are grouped into sockets: each socket consists of consecutive ports and each port belongs to exactly one socket. Note that the sockets at the bottom boundary may be of different lengths than those at the upper boundary. Lastly, a socket can be switched, in which case the order of ports in it is reversed.

Johnny learned through the grapevine that he is to be fired. He decided to have a little revenge--he is going to design the next chip so that it is as expensive in production, as possible. The key production cost is the number of layers, so he will switch each socket in a way to maximise the number of needed layers. This turned out to be much more difficult than his usual tasks and Johnny seeks your help.

입력

First line of the input contains a positive integer $n$ ($1 \le n \le 5\,000$) that denotes the number of ports on each boundary of the chip. The second line contains $n$ different positive integers from the set $\{1,2,\ldots, n\}$; these are the labels of ports on the bottom boundary (as a reminder: the labels on the consecutive ports on the upper boundary are $1, 2, \ldots, n$). The third row contains a positive integer $k$ ($1 \le k \le n$) denoting the number of sockets on the upper boundary, a single space, and then $k$ numbers denoting the amount of ports in the consecutive sockets of the upper boundary. Each socket has at least one port, the sum of sockets' numbers of ports on the upper boundary is equal to $n$. The fourth row contains a similar description of sockets on the bottom boundary.

출력

You should write a single positive integer: the maximal possible number of needed layers.

예제 입력 1

8
3 5 1 2 8 4 7 6
3 3 1 4
4 2 2 2 2

예제 출력 1

4

힌트

On the upper boundary the first socket contains ports $1, 2$ and  $3$, the second: port $4$, and the third: $5, 6, 7$ and $8$. By switching the sockets we can obtain the following sequences of ports on the upper boundary:

  • $(1, 2, 3)\quad (4)\quad (5, 6, 7, 8)$;
  • $(1, 2, 3)\quad (4)\quad (8, 7, 6, 5)$;
  • $(3, 2, 1)\quad (4)\quad (5, 6, 7, 8)$;
  • $(3, 2, 1)\quad (4)\quad (8, 7, 6, 5)$.