Minh đang được thầy giáo dạy về khái niệm nghịch thế. Thầy giáo cho Minh một dãy số nguyên dương ~A~ độ dài ~N~. Một nghịch thế trên một dãy là một cặp chỉ số ~(i, j)~ sao cho ~1 \le i < j \le N~ và ~A[i] > A[j]~.

Để thử kiến thức của Minh, thầy giáo bỏ lần lượt từng phần tử ra khỏi dãy và yêu cầu Minh tính lại số lượng nghịch thế của cả dãy sau khi phần tử đó được loại bỏ. Để tăng phần thách thức, thầy giáo yêu cầu sau mỗi lần một phần tử bị loại bỏ, Minh cần tìm ra đoạn con liên tiếp chỉ gồm các phần tử chưa bị loại bỏ sao cho lượng nghịch thế của đoạn con này là nhiều nhất. Một đoạn con liên tiếp thỏa mãn có thể được ký hiệu bằng hai số ~L, R~ (~1 \le L \le R \le N~) sao cho tất cả các phần tử ~k~ thỏa mãn ~L \le k \le R~ đều chưa bị loại bỏ.

Yêu cầu: Sau mỗi lần loại bỏ một phần tử, hãy tìm lượng nghịch thế nhiều nhất của một đoạn con liên tiếp các phần tử chưa bị loại bỏ.

Input

• Dòng đầu tiên là một số nguyên dương duy nhất ~N~ (~1 \le N \le 10^5~);
• Dòng tiếp theo là ~N~ số nguyên dương ~A[1], A[2], \dots, A[N]~ (~1 \le A[i] \le N~);
• Dòng tiếp theo là ~N~ số nguyên dương ~P[1], P[2], \dots, P[N]~ mô tả thứ tự các phần tử bị loại ra khỏi dãy:
  • Dãy số này được mã hóa;
  • Gọi ~last~ là đáp án trước khi bỏ phần tử thứ ~i~;
  • Ban đầu ~last~ bằng 0;
  • Phần tử thứ ~i~ bị loại khỏi dãy chính là ~last \oplus P[i]~;
  • Dữ liệu đảm bảo mỗi phần tử chỉ bị loại bỏ duy nhất một lần.

Output

• In ra ~N~ số, số thứ ~i~ là lượng nghịch thế nhiều nhất của một đoạn con liên tiếp chỉ gồm các phần tử chưa bị loại bỏ sau khi đã loại bỏ ~i~ phần tử.

Sample Input 1

4
4 3 2 1
2 0 5 3

Sample Output 1

1 1 0 0