The Little Elephant has two permutations a and b of length n, consisting of numbers from 1 to n, inclusive. Let's denote the i-th (1?≤?i?≤?n) element of the permutation a as ai, the j-th (1?≤?j?≤?n) element of the permutation b — as bj.
The distance between permutations a and b is the minimum absolute value of the difference between the positions of the occurrences of some number in a and in b. More formally, it's such minimum |i?-?j|, that ai?=?bj.
A cyclic shift number i (1?≤?i?≤?n) of permutation b consisting from n elements is a permutation bibi?+?1... bnb1b2... bi?-?1. Overall a permutation has n cyclic shifts.
The Little Elephant wonders, for all cyclic shifts of permutation b, what is the distance between the cyclic shift and permutation a?
Input
The first line contains a single integer n (1?≤?n?≤?105) — the size of the permutations. The second line contains permutation a as n distinct numbers from 1 to n, inclusive. The numbers are separated with single spaces. The third line contains permutation b in the same format.
Output
In n lines print n integers — the answers for cyclic shifts. Print the answers to the shifts in the order of the shifts' numeration in permutation b, that is, first for the 1-st cyclic shift, then for the 2-nd, and so on.
Examples
Input
2 1 2 2 1
Output
1 0
Input
4 2 1 3 4 3 4 2 1
Output
2 1 0 1
题意：
给你一个a数组，一个b数组，都只含1-n，俩数组的距离定义为，if(a[i]==b[j])dis=min(dis,abs(j-i))，然后对于每一个b向左循环移动的排列，让你输出距离。
分析：
若b[j]在a[i]的左边，随着每次左移，两点间dis+1
若b[j]在a[i]的右边，随着每次左移，两点间dis-1
每次的答案，从>=0的里面找最小的，<0的里面找最大的，两者再取最小对于如何模拟，举一个例子。
4
2 1 3 4
3 4 2 1
- 1.
将距离（pos_b[i]-pos_a[i])存入muliset里面：-2 -2 2 2
我们知道要找绝对值最小值，即找最接近0的，然后即s.lower_bound(0) ans=min(0-(-2),2-0)
我们更新距离要这么更新，首先删除b首个元素的距离，把他放在最后。
2 1 3 4
4 2 1 3
-2 2 2 2
- 2.
muliset里面现在为：-2 2 2 2，找最小值的话，我们应该找最接近1的，因为
对于两个数组，我们知道元素位置相差1才能是对应想等的
2 1 3 4
4 2 1 3
ans=min(1-(-2),2-1) ,因为我们在muliset实际情况没有减1，所以对于1左边的加一个1，1右边的减一个1.
其他步对应同理
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 2000000
int n,m,res;
int a[N],b[N];
int pos_a[N],pos_b[N];
multiset<int> s;
multiset<int>::iterator it;
void out()
{for(auto i:s)cout<<i<<" ";cout<<endl;
}
int main()
{scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);pos_a[a[i]]=i;}for(int i=0;i<n;i++){scanf("%d",&b[i]);s.insert(i-pos_a[b[i]]);}for(int i=0;i<n;i++){//cout<<i<<endl;//out();res=1e9;it=s.lower_bound(i);if(it!=s.end()){res=min(res,*it-i);}if(it!=s.begin()){res=min(res,i-*(--it));}printf("%d\n",res);it=s.find(i-pos_a[b[i]]);s.erase(it);s.insert(i-pos_a[b[i]]+n);}return 0;
}