Problem I
Horse Race
You are currently in a horse racing competition with your arch nemesis. Both you and your arch nemesis have $N$ horses. This race has $N$ rounds, where in each round, one of your horses will race against one of your nemesis’s horses. All horses only race once.
You possess $N$ horses currently arranged in a line. The $i$-th horse in this line will have speed $a_i$.
Your arch nemesis is sending out $N$ horses too, one per round. In each round, the horse with a higher speed will always win the race. If your horse and your opponent’s horse have the same speed, your horse will win.
You know the exact sequence in which your arch nemesis will send out their horses. The $i$-th horse in your nemesis’s ordering (which will run in the $i$-th round zero-indexed) will have speed $b_i$. Your arch nemesis has a specific strategy, which is to place the horses in a non-decreasing order of speed. Thus, $b_0 \leq b_1 \leq b_2 \dotsc \leq b_{n-1}$.
Since your horses are currently arranged in a line, it would take too much work to fully reorder them. Instead, you can pick any cyclic shift of the horses, and send them out in that order. We consider the $i$-th ($0 \leq i \leq N - 1$) cyclic shift to be the cyclic shift where the first $i$ horses are sent to the back.
You win the competition if, in the ordering you choose, you win all the individual races. Print the number of cyclic shifts that results in you winning the competition!
Input
The first line of the input consists of a single integer $n$ ($1 \leq n \leq 5 \cdot 10^5$), representing the number of rounds in the race. The second line of the input consists of $n$ integers $a_1, a_2, \dots , a_n$ ($0 \leq a_i \leq 10^9$), where $a_i$ represents the speed of your $i$-th horse in the line. The third line of the input consists of $n$ integers $b_1, b_2, \dots , b_n$ ($0 \leq b_i \leq 10^9$), where $b_i$ represents the speed of the $i$-th horse in your arch nemesis’ ordering. It is guaranteed that $b_0 \leq b_1 \leq b_2 \dotsc \leq b_{n-1}$.
Output
Output a single integer, the number of cyclic shifts of your horses that result in you winning all individual horse races.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 4 7 1 5 6 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 3 6 9 12 15 1 2 3 4 5 |
3 |
