蓝桥村的村长为了庆祝这个重要的节日，特意煮了 $N$ 碗元宵，准备分发给村民们。其中，第 $i$ 碗元宵里有 $A_i$ 颗元宵。村长原本计划将其中元宵数量较少的 $\lfloor\dfrac{N}{2} \rfloor$ 碗分给村里的小朋友们，但这一决定却引起了小朋友们的不满。他们觉得这样的分配方式不公平，纷纷抱怨起来。

面对小朋友们的抗议，村长灵机一动，提出了一个有趣的挑战：“这样吧，我给你们一个机会，让你们通过自己的智慧获得更多的元宵。我会给你们一个整数 $K$ ，你们可以进行 $N-K$ 次操作。在第 $i$ 次操作中（ $i$ 从 $1$ 到 $N-K$ ），你们可以从区间 $[i, i+K]$ 中选择两碗不同的元宵，将其中一碗的全部元宵倒入另一碗中。操作完成后，我仍然会将元宵数量较少的 $\lfloor\dfrac{N}{2} \rfloor$ 碗分给你们。”

小朋友们听了村长的提议，一时之间有些摸不着头脑。他们纷纷将目光投向了村里最聪明的你，希望你能帮助他们计算出，通过这样的操作，他们最多能获得多少颗元宵。

输入格式

第一行输入两个整数 $N$ 和 $K$ （ $2 \leq N \leq 10^5$ ， $1 \leq K \leq N-1$ ），分别表示元宵的碗数和村长给定的数字。

第二行输入 $N$ 个整数 $A_1, A_2, A_3, \cdots, A_N$ （ $1 \leq A_i \leq 10^9$ ），表示每碗元宵中的元宵数量。

输出格式

输出一个整数，表示小朋友们最多能获得的元宵数量。

样例输入

5 4
2 1 4 4 5

样例输出

说明

初始状态： $[2, 1, 4, 4, 5]$ 。
将第 $2$ 碗的元宵倒入第 $1$ 碗，得到 $[3, 0, 4, 4, 5]$
最终，将元宵数量较少的 $\lfloor\dfrac{5}{2} \rfloor = 2$ 碗分给小朋友们，即第 $1$ 碗和第 $2$ 碗，总共获得 $3 + 0 = 3$ 颗元宵。

T4. 摆放汤圆【算法赛】

问题描述

元宵节到了，老王家的汤圆摊前热闹非凡，顾客们排着长队等着品尝美味的汤圆。老王一边忙活，一边琢磨着怎么把汤圆摆得既好看又吉利。

老王家的汤圆盘是一个正方形的盘子，上面有 $n \times n$ 个格子，整齐地排列成 $n$ 行 $n$ 列的方阵。为了让顾客们眼前一亮，老王决定在盘子上摆放 $n$ 个大汤圆。

不过，老王这人有点强迫症，摆汤圆得遵守几条规矩：

同一列的格子里不能放两个汤圆，不然会挤到。
同一行的格子里也不能放两个汤圆，不然会滚走。
最重要的是，为了体现元宵节的对称美，汤圆的摆放必须关于对角线（从左上到右下的直线）对称。对角线上的格子本身就满足对称性。

老王想了半天，也没算出来到底有多少种摆法。他挠了挠头，决定找你帮忙。现在，请你帮老王算算，满足这些条件的汤圆摆放方案数一共有多少种？由于答案可能很大，你只需要输出方案数对 $10^9 + 7$ 取模后的结果即可。

输入格式

第一行包含一个整数 $t$ $(1 \leq t \leq 10^5)$ ，表示测试用例的数量。

接下来的 $t$ 行，每行包含一个整数 $n$ （ $1\leq n\leq 10^6$ ），表示盘子的大小。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示满足条件的汤圆摆放方案数。由于答案可能很大，你只需要输出方案数对 $10^9 + 7$ 取模后的结果即可。

样例输入

样例输出

1
2
4

T5. 元宵交友【算法赛】

问题描述

元宵节到了，小蓝决定举办一场热闹的交友活动，邀请她的朋友们一起赏灯、猜灯谜、吃汤圆！小蓝有 $n$ 个朋友，每个朋友都有一个独特的“元宵节参与度”，用数字 $a_i$ 来表示。参与度越高，说明这个朋友越喜欢元宵节的活动！

不过，小蓝的朋友们之间有一个有趣的“熟悉规则”：如果两个朋友的参与度相差太小（即 $|a_i - a_j| < k$ ），他们就会变得很熟悉，甚至会一起组队猜灯谜、抢汤圆！小蓝希望邀请尽可能多的朋友来参加活动，但她不希望被邀请的朋友之间太熟悉，否则活动可能会变得太热闹，甚至失控！

换句话说，如果小蓝邀请了一组朋友 $S = {x_1, x_2, \ldots, x_m}$ ，那么对于这组朋友中的任意两个人 $x_i$ 和 $x_j$ （ $i \neq j$ ），他们的参与度必须满足 $|a_{x_i} - a_{x_j}| \geq k$ 。这样才能保证他们之间不会太熟悉，活动也能顺利进行。

小蓝现在想知道，对于每个可能的 $k$ （ $1 \leq k \leq n$ ），她最多能邀请多少个朋友来参加活动，同时满足上述条件。

输入格式

第一行包含一个整数 $n$ （ $1 \leq n \leq 10^6$ ），表示小蓝的朋友数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $-5 \times 10^5 \leq a_i \leq 5 \times 10^5$ ），表示每个朋友的参与度。

输出格式

输出 $n$ 个整数，第 $i$ 个整数表示当 $k = i$ 时，小蓝最多能邀请多少个朋友。

样例输入

6
-1 4 3 8 4 -3

样例输出

5 4 3 3 3 2

说明

当 $k = 1$ 时，小蓝可以邀请所有朋友（除了重复的参与度），最多邀请 $5$ 个朋友。

当 $k = 2$ 时，小蓝可以邀请 $4$ 个朋友，比如参与度为 $-3, -1, 3, 8$ 的朋友。

当 $k = 3$ 时，小蓝可以邀请 $3$ 个朋友，比如参与度为 $-3, 3, 8$ 的朋友。

当 $k = 4$ 时，小蓝可以邀请 $3$ 个朋友，比如参与度为 $-3, 4, 8$ 的朋友。

当 $k = 5$ 时，小蓝可以邀请 $3$ 个朋友，比如参与度为 $-3, 3,8$ 的朋友。

当 $k = 6$ 时，小蓝只能邀请 $2$ 个朋友，比如参与度为 $-3, 8$ 的朋友。

T6. 灯笼大乱斗【算法赛】

问题描述

元宵佳节，一场别开生面的灯笼大赛热闹非凡。 $N$ 位技艺精湛的灯笼师依次落座，每位师傅都有相应的资历值，其中第 $i$ 位师傅的资历值为 $A_i$ 。从左到右，师傅们的资历值逐级递增（即 $A_1 < A_2 < \cdots < A_N$ ）。同时，每位师傅都带来了自己精心制作的灯笼，其亮度值依次为 $B_1, B_2, \cdots, B_N$ 。

大赛中，主持人会选择一个区间 $[L, R]$ （ $1 \leq L < R \leq N$ ），让这个区间内的师傅们进行两两比拼，构成一场“灯笼大乱斗”。

比拼规则如下：假设在区间 $[L, R]$ 中，由师傅 $i$ 和师傅 $j$ （ $L \leq i < j \leq R$ ）进行对决。对决双方分别持有自己的灯笼。

如果师傅 $i$ 的灯笼亮度 $B_i$ 小于师傅 $j$ 的灯笼亮度 $B_j$ ，则双方交换灯笼（相应地，如果 $B_i \geq B_j$ ，则不交换）。
双方最终的得分计算方式为：资历值 + 持有灯笼的亮度。得分高者获胜，得分相同则平局。

由于在比赛中，资历深的师傅输给资历浅的师傅，将会有损颜面。因此，为了避免这种情况发生，主持人需要选择必胜区间。

必胜区间定义：如果一个区间内任意两位师傅进行比赛，资历值高的师傅都必定能够获胜，则称该区间为必胜区间。

现在，请你帮主持人算算，必胜区间共有多少个？

输入格式

第一行包含一个整数 $N$ $(1 \leq N \leq 10^5)$ ，表示灯笼师傅的数量。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$ $(1 \leq A_i \leq 10^9)$ ，表示每位师傅的资历值，满足 $A_1 < A_2 < \cdots < A_N$ 。

第三行包含 $N$ 个整数 $B_1, B_2, \ldots, B_N$ $(1 \leq B_i \leq 10^9)$ ，表示每位师傅的灯笼亮度值。

输出格式

输出一个整数，表示必胜区间的总数量。

样例输入

3
1 3 5
3 4 1

0222 第 26 场 蓝桥月赛

0222 第 26 场蓝桥月赛