Description

不训练，打混，只能当咸鱼。 现给出一个序列 A 和一个序列 B 对于序列中 的 A[i] 而言，定义它的咸鱼值 min(A[i],A[i-1]……A[i-B[i]+1])*max(A[i],A[i-1]……A[i-B[i]+1])。 现在咸鱼王想知道每个数的咸鱼值，你能告诉她吗

Input Format

第一行一个整数 N。 接下来一行 N 个整数，分别表示 A[i]。 接下来一行 N 个整数，分别表示 B[i]。 题目保证 B[i] <= i , |A[i]|<=10^9。

Output Format

输出 N 行，依次表示第 i 个位置的咸鱼值

5
1 2 3 4 5
1 2 1 2 3

1
2
9
12
15

Hint

100%的数据保证： N <= 10^5 ,1 <= B[i] <= i , |A[i]|<=10^9

Source

线段树