Rar the Cat has invited N of his animal friends for a race. As some species can naturally move faster than others, Rar the Cat decided to normalise their differences by allocating different starting positions to each animal. The ith animal will start at position Pi, the higher the animal's position, the earlier it is in the line up and the closer it is to the finishing line.
The race has since concluded and Rar the Cat has recorded the total time (in seconds) of which of his animal friends have taken to complete the race from their respective starting positions. The time taken for the ith animal is Ti.
Given these values, Rar the Cat is interested in how many over-taking has taken place during the race, assuming that all of his animal friends run at a constant speed throughout the race. In other words, they do not slow down or speed up in the middle of the race.
An animal A is said to have over-taken another animal B where at some point in time, A was a further distance away from the finishing point than B but caught up and A ended up being in a shorter distance away from the finishing point than B at a later point in time.
Do note that based on the above definition, when 2 animals share a starting position or complete the race at the same time, they are deemed to have not over-taken each other.
The first line of input will contain one integer, N, the number of animals participating in the race.
The second line of input will contain N integers, the ith integer will be Pi.
The third line of input will also contain N integers, the ith integer will be Ti.
The output should contain one integer, the total number of over-takings in the entire race.
For all testcases, 0 ≤ Pi ≤ 109, 0 ≤ Ti ≤ 109.
Subtask 1 (9%): 1 ≤ N ≤ 2.
Subtask 2 (39%): 1 ≤ N ≤ 2000.
Subtask 3 (32%): 1 ≤ N ≤ 200000. However, no two animals share the same starting position and no two animals end at the same time.
Subtask 4 (20%): 1 ≤ N ≤ 200000.
Subtask 5 (0%): Sample Testcases
Sample Testcase 1
Animal 1 started further away from the finishing line, yet finished earlier than Animal 2. Hence, Animal 1 must have overtaken Animal 2 in the middle of the race.
Sample Testcase 2
1 2 3 4 5
30 20 30 20 10
Animal 2 started further away from the finishing line, yet finished earlier than Animal 3. Hence, Animal 2 must have overtaken Animal 3 in the middle of the race.
Sample Testcase 3
1 2 3 4 5
10 20 30 40 50
Animal 1 started the furthest away from the finishing line, yet finished earlier than Animals 2, 3, 4 and 5. Hence, Animal 1 must have overtaken all 4 other animals during the race.
Animal 2 started further from the finishing line as compared to Animals 3, 4 and 5. Yet, Animal 2 finished earlier than Animals 3, 4 and 5. Hence, Animal 2 must have overtaken these 3 animals during the race.
A similar argument holds for Animal 3 compared to Animals 4 and 5. Hence, Animal 3 must have overtaken 2 animals during the race.
Animal 4 started further away from the finishing line, yet finished earlier than Animal 5. Hence, Animal 4 must have overtaken Animal 5 in the middle of the race.
In total, there are 10 over-takings, 4 by Animal 1, 3 by Animal 2, 2 by Animal 3 and 1 by Animal 1.