Maximum Subrectangle Area after Decrement Operations

lhm has n rectangles of width 1 arranged in a row. The height of the i-th rectangle is given by $$a_i$$. He will perform k operations. In each operation, he selects one rectangle and reduces its height by 1. It is guaranteed that in every operation the height of any rectangle will remain at least 0.

After each operation, output the maximum area of any contiguous subrectangle that can be formed. A subrectangle is defined by a contiguous block of rectangles. The area is computed as the minimum height in the block multiplied by the number of rectangles (width). Formally, for a block of rectangles from index L to R, the area is:

$$\text{Area} = \min_{L \leq i \leq R} a_i \times (R - L + 1)$$

Your task is to output the maximum subrectangle area after each operation.

inputFormat

The input consists of the following lines:

• The first line contains two integers n and k denoting the number of rectangles and the number of operations.
• The second line contains n integers $$a_1, a_2, \dots, a_n$$ representing the initial heights of the rectangles.
• The third line contains k integers, each an index (1-indexed) indicating which rectangle's height is to be decremented by 1 in that operation.

It is guaranteed that all operations are valid (i.e. no rectangle's height will become negative).

outputFormat

Output k lines. The i-th line should contain a single integer representing the maximum subrectangle area after the i-th operation.

sample

5 3
2 3 2 5 1
2 4 3

8
8
4