Powerful Task#12240
Sign in

Powerful Task

1 second
256 megabytes
Hard

Well, this is quite a powerful task

— @denisovkostya

Everyone knows that Kostya is a fan of everything powerful.

This time, he got his hands on two arrays and of length . He came up with his special powerful characteristic. The power of two arrays of the same length is defined as the number of indices for which a_i = b_i.

However, simply counting the power, in his opinion, is not powerful enough. Therefore, he invented three powerful operations:

  1. Replace a_{i-1} with a_i - 1 for any (2 \leq i \leq |a|). He can apply this operation any number of times.

  2. Replace b_{i-1} with b_i - 1 for any (2 \leq i \leq |a|). He can apply this operation any number of times.

  3. Choose an index (1 \leq i \leq n) and remove a_i and b_i, thereby reducing the length of both arrays by one. He can apply this operation no more than once, and only if the operations of the second and first types have not yet been applied.

Help Kostya find the maximum possible power of the arrays and after applying his powerful operations.

Input

The first line contains a single integer (1 \leq n \leq 2 \cdot 10^5) — the length of the arrays and .

The second line contains the array of length (1 \leq a_i \leq 10^6).

The third line contains the array of length (1 \leq b_i \leq 10^6).

Output

Output a single number — the power of the arrays and .

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the first example:

We have the array a = \{12, 17, 7, 8, 9\} and b = \{7, 9, 2, 1, 8\}.

We apply the third operation for i = 4.

Then a = \{12, 17, 7, 9\} and b = \{7, 9, 2, 8\}.

We apply the first operation for i = 3.

Then a = \{12, 6, 7, 9\} and b = \{7, 9, 2, 8\}.

We apply the first operation for i = 2.

Then a = \{5, 6, 7, 9\} and b = \{7, 9, 2, 8\}.

We apply the second operation for i = 4.

Then a = \{5, 6, 7, 9\} and b = \{7, 9, 7, 8\}.

We apply the second operation for i = 3.

Then a = \{5, 6, 7, 9\} and b = \{7, 6, 7, 8\}.

We apply the second operation for i = 2.

Then a = \{5, 6, 7, 9\} and b = \{5, 6, 7, 8\}.

Then the power of the arrays and is equal to since for i = \{2, 3, 4\} it holds that a_i = b_i.

Scoring

  1. Subtask ( points): n \leq 10

  2. Subtask ( points): n \leq 100

  3. Subtask ( points): n \leq 5 \cdot 10^3

  4. Subtask ( points): a_i \leq 100

  5. Subtask ( points): and are permutations

  6. Subtask ( points): Without additional constraints