Alice and Bob were playing a game yet again but this time, Bob already lost the game. Now he wants to take revenge.

Bob saw a jigsaw puzzle which was solved by Alice and decided to jumble the puzzle pieces again. There are N puzzle pieces in a line numbered from 1 to N in increasing order and he has K minutes before Alice catches him.  
Bob can swap any two pieces of the puzzle. Each swap takes 1 minute, and so Bob can make at most K swaps.

Let A_{i} denote the piece in the i-th position after Bob finishes making his swaps.

Alice's *angriness* is defined to be the number of pairs (i, j) such that 1 ≤ i < j ≤ N and A_{i} > A_{j}.

Bob would like to make Alice as angry as possible, so he asks for your help: if he performs his swaps optimally, what is the maximum *angriness* he can achieve?

------ Input Format ------ 

- The first line of input contains an integer T, denoting the number of test cases.
- The first and only line of each test case contains two space-separated integers N and K: the number of pieces and the number of swaps Bob can make.

------ Output Format ------ 

- For each test case, output on a new line a single integer: Alice's maximum possible angriness.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{9}$
$1 ≤ K ≤ 10^{9}$

----- Sample Input 1 ------ 
4
7 3
1 4
8 2
5 3

----- Sample Output 1 ------ 
21
0
22
10

----- explanation 1 ------ 
Test case $1$: $N = 7$, so the pieces are initially arranged as $[1, 2, 3, 4, 5, 6, 7]$. Bob can make $K = 3$ swaps. One optimal way of swapping is as follows:
- First, swap $2$ and $6$. Now the pieces are $[1, 6, 3, 4, 5, 2, 7]$
- Next, swap $1$ and $7$. Now the pieces are $[7, 6, 3, 4, 5, 2, 1]$
- Finally, swap $3$ and $5$. Now the pieces are $[7, 6, 5, 4, 3, 2, 1]$

The angriness of this sequence is $21$, which is the maximum possible.

Test case $2$: $N = 1$, so no swaps can be made. The answer is always $0$.

Source: codechef | Difficulty: MEDIUM
Tags: Mathematics

Greedy algorithms


Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	total = 0
	if k >= n // 2:
		print(n * (n - 1) // 2)
		continue
	else:
		total += n * (n - 1) // 2
		total -= (n - k) * (n - k - 1) // 2
		total += (n - 2 * k) * k
		total += k * (k - 1) // 2
	print(total)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	k = min(n // 2, k)
	t = (n - 1) * k
	l = n - 2 * k
	t += k * l
	print(t)


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 1:
		print(0)
	elif n // 2 <= k:
		print(n * (n - 1) // 2)
	else:
		tot = 0
		x = n - k
		tot += n * (n - 1) // 2 - x * (x - 1) // 2
		con = n - 2 * k
		tot += k * con
		tot += k * (k - 1) // 2
		print(tot)


def getSummation(n):
	return (n - 1) * (n - 1 + 1) // 2

def getSummation1(n, k):
	ans = n - 1
	itr = ans - 1
	for _ in range(k - 1):
		ans += itr
		itr -= 1
	return ans
t = int(input())
while t:
	(n, k) = map(int, input().split())
	if k == 0:
		print(0)
		t -= 1
		continue
	if k >= n // 2:
		print(getSummation(n))
	else:
		print(getSummation(n) - getSummation(n - k) + (n - k * 2) * k + getSummation(k))
	t -= 1


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	f = x * (x - 1) // 2
	h = 0
	if y < x / 2:
		h = x - 2 * y
		f = f - h * (h - 1) // 2
	print(f)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	xn = n // 2
	if k >= xn:
		print(n * (n - 1) // 2)
	else:
		a = n * (n - 1) // 2
		x = n - 2 * k - 1
		b = x * (x + 1) // 2
		print(a - b)


def solve():
	(n, k) = map(int, input().split())
	if k > n // 2:
		k = n // 2
	print(k * (2 * n - 2 * k - 1))
for _ in range(int(input())):
	solve()


import sys
from math import gcd, sqrt, log, ceil, floor
tc = int(input().strip())
for t in range(tc):
	(n, k) = map(int, input().split())
	if n == 1:
		print(0)
		continue
	if k >= n // 2:
		print(n * (n - 1) // 2)
		continue
	anger = 0
	anger += n * (n - 1) // 2 - (n - k) * (n - k - 1) // 2
	anger += k * (n - 2 * k)
	anger += k * (k - 1) // 2
	print(anger)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = n * (n - 1) // 2
	l = 0
	if k < n / 2:
		l = n - 2 * k
		ans = ans - l * (l - 1) // 2
	print(int(ans))


import sys
from bisect import bisect_left as bl, bisect_right as br, bisect
from collections import defaultdict as dd, deque, Counter
from heapq import merge, heapify, heappop, heappush, nsmallest
from itertools import combinations
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log

def inp():
	return sys.stdin.readline().strip()

def iinp():
	return int(inp())

def mp():
	return map(int, inp().split())

def liinp():
	return list(mp())

def lmps():
	return list(map(str, inp()))

def solve(n, k):
	k = min(k, n // 2)
	ans = k * (2 * n - 2 * k - 1)
	return ans
tc = iinp()
for _ in range(tc):
	(n, k) = liinp()
	print(solve(n, k))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	sum1 = 0
	if k < n // 2:
		j = n - k
		sum1 += n * (n - 1) // 2 - j * (j - 1) // 2
		sum1 += (n - k - k) * k
		sum1 += k * (k - 1) // 2
	else:
		sum1 = n * (n - 1) // 2
	print(sum1)


testcases = int(input())
for eachcase in range(testcases):
	(length, moves) = map(int, input().split())
	ans = length * (length - 1) // 2
	if moves < length // 2:
		noswap = length - 2 * moves
		nopairs = noswap * (noswap - 1) // 2
		ans = ans - nopairs
	print(ans)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	s = a * (a - 1) // 2
	f = a - 2 * b
	if b < a / 2:
		s = s - f * (f - 1) // 2
	print(s)


for x in range(int(input())):
	(n, k) = map(int, input().split())
	totalPairs = n * (n - 1) // 2
	if n // 2 > k:
		notSwapped = n - 2 * k
		pairsNotSwapped = notSwapped * (notSwapped - 1) // 2
		totalPairs = totalPairs - pairsNotSwapped
	print(totalPairs)


T = int(input())
while T:
	T -= 1
	(n, k) = list(map(int, input().split()))
	if n == 1 or k == 0:
		print(0)
	elif k >= n // 2:
		print(n * (n - 1) // 2)
	else:
		j = k * (k * 2 - 1)
		l = n - k * 2
		print(j + l * k * 2)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	mid = n // 2
	if n == 1:
		print(0)
	elif mid < k:
		print(n * (n - 1) // 2)
	else:
		p = n - 2 * k
		t = n * (n - 1) // 2 - p * (p - 1) // 2
		print(t)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	sum = n * (n - 1) // 2
	if k < n // 2:
		x = n - 2 * k
		sum -= x * (x - 1) // 2
	print(sum)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	k = min(k, n // 2)
	print(n * (n - 1) // 2 - (n - k) * (n - k - 1) // 2 + (k - 1) * k // 2 + (n - 2 * k) * k)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	if n == 1:
		print(0)
	elif k >= n // 2:
		print(n * (n - 1) // 2)
	else:
		print((2 * n - 2 * k - 1) * k)


t = input()
for c in range(0, int(t)):
	(length, moves) = map(int, input().split())
	ans = length * (length - 1) // 2
	if moves < length // 2:
		noswap = length - 2 * moves
		nopairs = noswap * (noswap - 1) // 2
		ans = ans - nopairs
	print(ans)


def sigma(n):
	s = n * (n + 1) // 2
	return s
T = int(input())
for tc in range(T):
	s = 0
	(n, k) = map(int, input().split(' '))
	if k >= n // 2:
		print(sigma(n - 1))
	else:
		s += sigma(n - 1) - sigma(n - k - 1)
		s += sigma(k - 1)
		s += (n - 2 * k) * k
		print(s)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	if k >= n // 2:
		print(n * (n - 1) // 2)
	else:
		print(k * (2 * n - 3 - (k - 1) * 2))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	m = n // 2
	if n == 1:
		print(0)
	elif m <= k:
		a = n * (n - 1) // 2
		print(a)
	else:
		b = n * (n - 1) // 2
		c = n - 2 * k
		c = c * (c - 1) // 2
		print(b - c)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = a // 2
	s = 0
	if b >= c:
		c = a - 1
		s = c * (c + 1) // 2
	else:
		s = -2 * b ** 2 + 2 * (b * a) - b
	print(s)


T = int(input())
for i in range(0, T):
	temp = input().split()
	N = int(temp[0])
	K = int(temp[1])
	var2 = 0
	if K >= int(N // 2):
		var2 = (N - 1) * N // 2
	else:
		var2 = -2 * K ** 2 + 2 * (K * N) - K
	print(int(var2))


T = int(input())
for t in range(T):
	temp = input().split()
	N = int(temp[0])
	K = int(temp[1])
	if N == 1:
		print(0)
	elif K >= N // 2:
		print((N - 1) * N // 2)
	else:
		s = -2 * K * K + 2 * N * K - K
		print(s)


for x in range(int(input())):
	(n, k) = map(int, input().split())
	if k > n // 2:
		print(int(n * (n - 1) // 2))
	else:
		a = n * (n - 1) // 2 - (n - k - 1) * (n - k) // 2
		print(a + (n - 2 * k) * k + k * (k - 1) // 2)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	if N == 1:
		print(0)
	elif K >= N // 2:
		print(N * (N - 1) // 2)
	else:
		print(K * (N - 1 + (N - 2 * K)))


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	s = N * (N - 1) // 2
	if N / 2 > K:
		y = N - 2 * K
		s -= y * (y - 1) // 2
	print(s)


T = int(input())
for t in range(T):
	s = input().split()
	n = int(s[0])
	k = int(s[1])
	if n == 1:
		print(0)
	elif n == 2 and k % 2 == 0:
		print(0)
	elif n == 2 and k % 2 != 0:
		print(1)
	elif k <= n // 2:
		ans = n * k - k + (n - 2 * k) * k
		print(ans)
	else:
		k = n // 2
		ans = n * k - k + (n - 2 * k) * k
		print(ans)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	no = n // 2
	if no <= k:
		print(n * (n - 1) // 2)
	elif n == 1:
		print(0)
	else:
		ans = n * (n - 1) // 2
		r = n - 2 * k
		se = r * (r - 1) // 2
		ans = ans - se
		print(ans)


def func(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	ans = 0
	(n, k) = list(map(int, input().split()))
	m = n // 2
	if k >= m:
		print(func(n - 1))
	else:
		ans = func(n) - func(n - k) - k
		me = n - 2 * k
		ans += me * k
		ans += func(k - 1)
		print(ans)


def sum_upto_n(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	(n, k) = map(int, input().strip().split())
	k = min(k, n // 2)
	q1 = sum_upto_n(n - 1) - sum_upto_n(n - k - 1)
	q2 = (n - 2 * k) * k
	q3 = sum_upto_n(k - 1)
	print(q1 + q2 + q3)


time = int(input())
for _ in range(time):
	(n, k) = map(int, input().split())
	a = n * (n - 1) // 2
	if k < n // 2:
		b = n - 2 * k
		a -= b * (b - 1) // 2
	print(a)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	value = n * (n - 1) // 2
	if n <= 2 * k:
		print(value)
	else:
		a = n - 2 * k
		sub_value = value - a * (a - 1) // 2
		print(sub_value)


T = int(input())
for x in range(T):
	(N, K) = map(int, input().split())
	if K >= N // 2:
		print(int(N * (N - 1) // 2))
	else:
		print(K * (2 * (N - K) - 1))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = n * (n - 1) // 2
	if n <= 2 * k:
		print(l)
	else:
		a = n - 2 * k
		l = l - a * (a - 1) // 2
		print(l)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	s = N * (N - 1) // 2
	if N <= 2 * K:
		print(s)
	else:
		a = N - 2 * K
		s = s - a * (a - 1) // 2
		print(s)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	ans = n * (n - 1) // 2
	if k < n // 2:
		temp = n - 2 * k
		ans -= temp * (temp - 1) // 2
	print(ans)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = n * (n - 1) // 2
	if n <= 2 * k:
		print(s)
	else:
		a = n - 2 * k
		s = s - a * (a - 1) // 2
		print(s)


tc = int(input())
for i in range(tc):
	arr = input().split(' ')
	n = int(arr[0])
	k = int(arr[1])
	if 2 * k >= n:
		print((n - 1) * n // 2)
	else:
		print(2 * n * k - 2 * k * k - k)


t = int(input())
for _ in range(0, t):
	(n, k) = map(int, input().split())
	if n == 1:
		print(0)
		continue
	if n < 2 * k:
		k = n // 2
	print((2 * (n - k) - 1) * k)


numberofcases = int(input())

def sum(n):
	return n * (n + 1) / 2
for case in range(numberofcases):
	inputs = input().split(' ')
	pieces = int(inputs[0])
	swaps = int(inputs[1])
	swapp = min(swaps, pieces // 2)
	if pieces >= 2:
		print(swapp * (pieces + pieces - 2 * swapp + 2) - 3 * swapp)
	else:
		print(0)


n = int(input())
for i in range(n):
	(N, K) = map(int, input().split(' '))
	if K >= N // 2:
		print(N * (N - 1) // 2)
	else:
		print(K * N - K * (K + 1) // 2 + (N - K * 2) * K + (K - 1) * K // 2)


for _ in range(int(input())):
	sum1 = 0
	(n, k) = map(int, input().split())
	p = n
	t = n - k
	if k >= n // 2:
		print(n * (n - 1) // 2)
	else:
		sum1 += p * (p - 1) // 2 - t * (t - 1) // 2
		sum1 += k * (p - 2 * k) + k * (k - 1) // 2
		print(sum1)


def summ(n):
	return n * (n + 1) // 2
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	step = min(n // 2, k)
	if n % 2 == 0:
		rem = (n // 2 - step) * 2 - 1
	else:
		rem = (n // 2 - step) * 2
	ang = summ(n - 1) - summ(rem)
	print(ang)


def ans(n, k):
	if k >= n // 2:
		return n * (n - 1) // 2
	else:
		not_swapped = n - 2 * k
		return n * (n - 1) // 2 - not_swapped * (not_swapped - 1) // 2
test_cases = int(input())
while test_cases != 0:
	d = list(map(int, input().split()))
	print(ans(d[0], d[1]))
	test_cases -= 1


for _ in range(int(input())):
	(n, b) = map(int, input().split())
	if n // 2 <= b:
		s = (n - 1) * n // 2
		print(s)
	else:
		s = (n - 1 - b * 2) * b + b * (b + 1) // 2 + (n - 1) * n // 2 - (n - b - 1) * (n - b) // 2
		print(s)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	if N == 1:
		print(0)
	else:
		p = N - min(K * 2, N - 1) - 1
		x = 0
		x = N - 1
		print(x * (x + 1) // 2 - p * (p + 1) // 2)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	x = a * (a - 1) // 2
	if b > a // 2:
		print(x)
	else:
		c = a - b * 2
		y = c * (c - 1) // 2
		print(x - y)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s1 = n * (n - 1) // 2
	if m > n // 2:
		print(s1)
	else:
		k = n - m * 2
		s2 = k * (k - 1) // 2
		print(s1 - s2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k >= n // 2:
		print(n * (n - 1) // 2)
	else:
		val = k * (k - 1) // 2
		val += (n - 2 * k) * k
		req = n - k - 1
		temp = n * (n - 1) // 2 - req * (req + 1) // 2
		val += temp
		print(val)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	k = min(k, n // 2)
	ans = (n - 1) * k + (n - 2 * k) * k
	print(ans)