This question appeared on HackWithInfy 2022

Problem Statement

You are given an array of length N containing a permutation of the first N natural numbers i.e (1 to N). You are able to apply the following operation at most once.

• Choose any subarray of size K and reverse it.

Return the minimum inversions in the array after said operations.

Note — Inversion in an array is defined as a pair of indices (i,j) such that Ai > Aj and i < j.

Constraints

1 <= N <= 5 * 10^3

1 <= A[i] <= N

1 <= K <= N

Sample Test Case — 1

Arr = [1, 2, 3, 4], K = 2

Ans — 0

Explanation

Array initially has 0 inversions. Hence no need to apply any operations.

Sample Test Case — 2

Arr = [4, 3, 5, 1, 2], K = 2

Ans — 6

Explanation

If we reverse the subarray [4, 3], we get Arr = [3, 4, 5, 1, 2].

The resultant inversion is 6. It is the minimum that we can get.

Sample Test Case — 3

Arr = [1, 4, 2, 3, 5], K = 3

Ans — 1

Explanation

If we reverse the subarray [4, 2, 3], we get Arr = [1, 3, 2, 4, 5].

The resultant inversion is 1. It is the minimum that we can get.

Can anyone solve this problem ???