← 返回题目列表

Codeforces · 645/B

B. 顽皮的混乱制造者

中文机器翻译题面 查看原题

这是一个温暖的春天下午,农夫约翰的 n 头奶牛正在他们的摊位上思考切开的仙人掌。标记为 1 到 n 的奶牛经过排列,使得第 i 头奶牛占据从左侧算起的第 i 个栏位。然而,艾尔西意识到自己将永远生活在贝西聚光灯之外的阴影中,于是成立了恶作剧混乱制造者,并密谋破坏这美丽的田园节奏。当农夫约翰小睡 k 分钟时,埃尔西和混乱制造者计划重复选择两个不同的牛栏并交换占据这些牛栏的奶牛,每分钟交换不超过一头。

作为一丝不苟的恶作剧者,顽皮的混乱制造者想知道他们在 k 分钟内可以达到的最大混乱程度。我们将第 i 个栏位中的奶牛的标签表示为 pi。奶牛排列的混乱度定义为满足 i < j 且 pi > pj 的对 (i, j) 的数量。

输入

输入的第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 100 000) - 分别是奶牛的数量和 Farmer John 的午睡长度。

输出

输出一个整数,即恶作剧混乱制造者通过执行不超过 k 次交换所能达到的最大混乱程度。

示例

输入 #1

5 2

输出 #1

10

输入 #2

1 10

输出 #2

0

注意

在第一个示例中,恶作剧混乱制造者可以在第一分钟内交换畜栏 1 和 5 中的奶牛,然后在第二分钟内交换畜栏 2 和 4 中的奶牛。这颠倒了奶牛的排列,使我们的总混乱度为 10。

在第二个样本中,只有一头牛,因此最大可能的混乱度为 0。