2020“远光杯”网络资格赛L 捕鱼达人（树状数组/区间最大值/单点更新）

题目

门前大桥下，游过一群鱼，小红鱼，黄花鱼，绿草鱼，蓝顶鱼，粉鲳鱼，砂紫鱼，竟然在鱼塘中排成了一条队列，捕鱼达人坤坤打算将他们捕获。但是由于这些鱼比较稀有，坤坤需要在指定的规则下才能抓捕他们，规则如下：

1. 在捕鱼过程中当前捕获的鱼颜值必须大于等于前一条鱼颜值a_i，对于捕获的第一条鱼没有要求。

2. 每一条鱼变身后他的价值b_i为他的颜值的1/10000（整除）。

3. 每一条鱼变身后他的颜值会变成原本颜值对10000的余数，也就是a_i%10000。（例如变身前颜值a_i为20001，则变身后它的价值变为2，颜值变为1）。

4. 所有鱼在一开始的时候就会变身，变身后坤坤才可以开始捕鱼。

5. 鱼群顺序是从左到右排列的，鱼群的顺序是不可变的，坤坤可以从鱼群头或者鱼群尾开始捕鱼，但是顺序必须是从左到右或者从右到左。

6. 坤坤希望他捕获到的鱼的价值最多。

输入要求 第一行先输入一个T（1