跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F2709. Little Elephant and Shifts

  • ID: 2715
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:提高
  • 上传者:
  • 数据结构
  • 提高
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Little Elephant and Shifts

题目描述

C. Little Elephant and Shifts
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 2375 题。保留原作者与原赛事署名。