背景

wys是TKD的妹子。

wys听说TKD总把题面写得很长很长;

于是这一次她要求TKD把题面写得很短很短。

描述

给定一排n个柱子,第i个位置的高度为a_i

现在有m个操作,每次选择一个位置,将这个位置的高度减掉1

所有操作之前以及每次操作后输出当前的最大子矩形的大小

强制在线

输入格式

第一行两个正整数n,m,含义如题目中所示

接下来一行n个非负整数,第i个数a_i表示第i个位置的高度

接下来m行每行一个非负整数pos_i,代表将位置pos_i\oplus last\_ans的柱子高度-1

last\_ans表示上一次询问的答案,初始值为一开始的最大子矩形大小

输出格式

m+1行,每行一个正整数,代表第i-1次操作后的最大子矩形大小

样例输入

7 3
2 2 4 5 3 3 3
10
12
15

样例输出

15
14
10
8

数据范围与约定

  • 对于30%的数据:1\leq n,m\leq 1000
  • 对于另外20%的数据:1\leq n,m\leq10^5,a_i\leq 1
  • 对于100%的数据:1\leq n,m\leq10^5,a_i\leq10^6
     
    数据保证任何时刻所有位置的高度\geq 0

样例解释

四次询问的答案如下图所示:

来源

原创

提示

请注意输入和输出可能超过32位整型范围