F. Unlock the Chest
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Committee of the National Archeological Research in eXploration of Organized Zones (NARXOZ) found an old chest in the Almaty region. But there is a lock on the chest with the password that consists of $$$n$$$ positive numbers.

Luckily, scientists also found the correct version of this list — the one that opens the chest.

So, you are given the two lists of numbers: the password that is now on the lock and the password that opens the chest.

To change the current password into the correct one, you can use this operation:

  • Choose an index $$$i$$$ such that $$$1 \le i \lt n$$$.
  • Let $$$x$$$ = value at position $$$i$$$ before the operation. Let $$$y$$$ = value at position $$$i + 1$$$ before the operation.
  • After the operation: The number at position $$$i$$$ becomes $$$y - 1$$$. The number at position $$$i + 1$$$ becomes $$$x + 1$$$.

You can repeat this operation as many times as needed. Your goal is to make the current list exactly the same as the correct list, using the smallest number of operations.

If it is not possible to make the two lists the same, output -1.

NARXOZ is holding a contest: the fastest person who solves this problem will get a great job offer. You want to win — so get to work!

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 3*10^5$$$) — the length of the password.

The second line contains $$$n$$$ positive integers — the current version of the password.

The third line contains $$$n$$$ positive integers — the correct version of the password.

All values of the integers are positive and do not exceed $$$10^9$$$.

Output

Print one number — the minimum number of operations needed to turn the current list into the correct list. If it is impossible, print -1.

Examples
Input
3
4 7 3
1 7 6
Output
3
Input
4
3 1 4 2
2 2 3 3
Output
-1
Note

In the first sample we can perform operations in the following order: Swap $$$(1, 2)$$$, swap $$$(2, 3)$$$ and swap $$$(1, 2)$$$. It can be shown, that there is no other option with less number of operations.

In the second sample there is no valid order of operations to get the correct version of the password from the current one.