Assembling Venus Laboratory

There are n modules delivered to Venus to assemble a laboratory. The modules are placed in a row, and the height of the i-th module is \(h_i\). Initially, each module forms an independent segment, with segments numbered from 1 to n in order.

A special robot will perform the assembly by executing exactly n-1 merge instructions. Each instruction is represented by a number \(k_j\). When an instruction is executed, the segment with current index \(k_j\) and the segment immediately following it (i.e. with index \(k_j+1\)) are merged. After merging, the new segment takes the place of the two old ones and the segments are renumbered accordingly.

For any segment consisting of modules \(h_l, h_{l+1}, \dots, h_r\), the capacity of the segment is defined based on the water accumulation between modules. For any module at position \(p\) (l ≤ p ≤ r), define:

\[ l_p = \max\{ h_l, h_{l+1}, \dots, h_p \},\quad r_p = \max\{ h_p, h_{p+1}, \dots, h_r \} \]

Then the depth at module \(p\) is defined as:

\[ d_p = \min(l_p, r_p) - h_p \]

The capacity of the segment is \(w = d_l + d_{l+1} + \cdots + d_r\). After each merge instruction, you are required to output the capacity of the newly merged segment.

Input Format: The first line contains a positive integer \(n\) (the number of modules). The second line contains \(n\) integers: \(h_1, h_2, \dots, h_n\). Then follow \(n-1\) lines, each containing a merge instruction represented by an integer \(k_j\) (1-indexed) which indicates that the segment with the current index \(k_j\) and its following segment (index \(k_j+1\)) are merged.

Output Format: For each merge operation, output the capacity of the merged segment on a new line.

inputFormat

The input consists of:

• One integer \(n\) representing the number of modules.
• A line with \(n\) integers \(h_1, h_2, \dots, h_n\) (the heights of the modules).
• \(n-1\) lines each containing an integer \(k_j\) indicating a merge between the segment at index \(k_j\) and the segment immediately after it.

outputFormat

Output \(n-1\) lines. Each line should contain one integer: the capacity of the merged segment after each merge operation.

sample

3
2 1 2
1
1

0
1