Question
Best Restaurant
In order to become the best restaurant of the area, Issac(The Owner) wants to make as many of his customers happy.
There are N customers C0, C1,. . Cn-1 seating in a circular manner and ith of the N customers has dish Di in front of them.
The ith customer (Ci) will be happy if the dish i is in front of customer C(i+1)%N or Ci or C(i-1)%N
To maximise the happiness Issac can rotate the table anticlockwise so that the dish which was in front of customer Ci is now in front of customer C(i+1)%N
Calculate the maximum happiness that Issac can achieve.
There are N customers C0, C1,. . Cn-1 seating in a circular manner and ith of the N customers has dish Di in front of them.
The ith customer (Ci) will be happy if the dish i is in front of customer C(i+1)%N or Ci or C(i-1)%N
To maximise the happiness Issac can rotate the table anticlockwise so that the dish which was in front of customer Ci is now in front of customer C(i+1)%N
Calculate the maximum happiness that Issac can achieve.
Input
The first line of the input contains a single integer N
The second line contains N integers D0, D1,. . Dn-1 representing the initial arrangement of the dishes.
Constraints:
3 <= N <= 2 x 105
0 <= Ci <= N-1. All Ci are distinct.
0 <= Di <= N-1. All Di are distinct.
All values are integers.
The second line contains N integers D0, D1,. . Dn-1 representing the initial arrangement of the dishes.
Constraints:
3 <= N <= 2 x 105
0 <= Ci <= N-1. All Ci are distinct.
0 <= Di <= N-1. All Di are distinct.
All values are integers.
Output
Output the maximum happiness that is possible.
Example
Sample Input 1:
4
1 2 0 3
Sample Output 1:
4
Explanation 1:
Initial arrangement - > 1 2 0 3
Final arrangement - > 3 1 2 0
Person 0 is happy because Dish 0 is in front of Person 3 (=(0−1)mod4).
Person 1 is happy because Dish 1 is in front of Person 1 (=1).
Person 2 is happy because Dish 2 is in front of Person 2 (=2).
Person 3 is happy because Dish 3 is in front of Person 0 (=(3+1)mod4).
Sample Input 2:
3
0 1 2
Sample Output 2:
3
Sample Input 3:
10
3 9 6 1 7 2 8 0 5 4
Sample Output 3:
5
4
1 2 0 3
Sample Output 1:
4
Explanation 1:
Initial arrangement - > 1 2 0 3
Final arrangement - > 3 1 2 0
Person 0 is happy because Dish 0 is in front of Person 3 (=(0−1)mod4).
Person 1 is happy because Dish 1 is in front of Person 1 (=1).
Person 2 is happy because Dish 2 is in front of Person 2 (=2).
Person 3 is happy because Dish 3 is in front of Person 0 (=(3+1)mod4).
Sample Input 2:
3
0 1 2
Sample Output 2:
3
Sample Input 3:
10
3 9 6 1 7 2 8 0 5 4
Sample Output 3:
5