You are given an array A of N integers.

For every possible subarray, calculate its median. You need to determine the range of median values, i.e., the difference between the maximum possible median and the minimum possible median among all subarrays.

Input Format

The first line contains an integer N. The second line contains N integers A[i].

Output Format

Print a single integer representing:

maximum median - minimum median

Constraints

1 ≤ N ≤ 2 × 10^5 1 ≤ A[i] ≤ 10^9

Example

Input: 5 1 3 2 5 4

Output: 4

Explanation: The minimum possible median is 1, while the maximum possible median is 5. Therefore, the median range is 5 - 1 = 4.