Given an array of n integers, arr[n] , determine all of its subsequences S of three elements and find the validity of arr.

validity = min{3 * abs(mean(S) - median(S)) for all S}

A subsequence is a sequence that can be derived from a sequence by deleting zero or more elements without changing the order of the remaining elements, for example [3, 4] is a subsequence of [5, 3, 2, 4].

Note

mean(A) is the average of the array (the sum of the array divided by the size of the array).

median(A) is the middle value of an ordered set of numbers with an odd number of elements.

abs(x) is the absolute value of an integer.

Function Description

Complete the function calculateValidity in the editor.

calculateValidity has the following parameters:

• int arr[n] : the series of integers

Returns

int : the validity of the series of integers

Example 1 :

Input: arr = [2, 3, 1, 4]
Output: 0
Explanation: The subsequences of three elements from the array [2, 3, 1, 4] are [2, 3, 1], [2, 3, 4], [2, 1, 4], and [3, 1, 4]. The validity for each subsequence is calculated as follows:

[2, 3, 1]: mean = (2 + 3 + 1) / 3 = 2, median = 2, validity = 3 * |2 - 2| = 0

[2, 3, 4]: mean = (2 + 3 + 4) / 3 = 3, median = 3, validity = 3 * |3 - 3| = 0

[2, 1, 4]: mean = (2 + 1 + 4) / 3 = 2.33, median = 2, validity = 3 * |2.33 - 2| = 1

[3, 1, 4]: mean = (3 + 1 + 4) / 3 = 2.67, median = 3, validity = 3 * |2.67 - 3| = 1

The minimum validity among all subsequences is 0.

Example 2 :

Input: arr = [1, 2, 4]
Output: 1
Explanation: No explanation for now. Will provide it once find any :D

Constraints:

3 ≤ n ≤ 103

1 ≤ arr[i] ≤ 109

arr contains distinct elements.