One-Armed Bandit

Time limit1sMemory limit128 MB

Summary

Find the rotation of three symbol reels that maximizes the number of rows showing the same symbol three times.

Level: Medium6 of 10
Topics: Hash map, Math
Solved: No attempts yet

Problem

Bajtek walked into a casino and was immediately drawn to a one-armed bandit (a slot machine). The heart of the machine is its three reels. Each reel is split into $n$ equal fields, and each field is painted with one symbol. There are $n$ possible symbols, and every symbol appears on each reel exactly once. For simplicity, number the symbols from $1$ to $n$ . The picture below shows an example machine whose three reels are each split into $n = 5$ fields.

When the lever is pulled, each reel rotates cyclically by some number of positions. The player's payout depends on how many horizontal rows end up showing three identical symbols.

Bajtek knows the machine could take all of his money, so he first wants to figure out the best he could possibly do. Help him find the largest number of rows that can simultaneously show three identical symbols, over the most favorable rotation of the three reels.

Input

The first line contains a single integer $n$ ( $1 \le n \le 300000$ ), the size of each reel. The next three lines each describe the symbols on one reel.

Each reel is given as $n$ pairwise distinct integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le n$ ), where $a_i$ is the symbol at position $i$ .

Output

Print a single integer: the maximum number of rows that can simultaneously show three identical symbols.

Hint

In the sample, rotate reel 1 up by three positions, reel 2 up by one position, and reel 3 down by one position. With these rotations, three rows each show three identical symbols, so the answer is $3$ .

Examples1

Example 1
Input
```
5
1 5 4 3 2
1 3 2 4 5
2 1 5 4 3
```
Expected output
```
3
```