# Good Subarrays Count
## Problem Statement
You are given an array $a$ consisting of $n$ integers. A subarray is defined as a contiguous part of the array. We call a subarray "good" if it satisfies one of the following conditions:
1. The subarray has an odd length.
2. The subarray has an even length, say $L$. Let its elements, when sorted in non-decreasing order, be $b'_1, b'_2, \dots, b'_L$. The condition for it to be good is that its two middle elements are equal, i.e., $b'_{L/2} = b'_{L/2+1}$ (using 1-based indexing for the sorted elements).
Your task is to find the total number of "good" subarrays in the given array $a$.
## Input Format
- First line: An integer $n$ ($1 \le n \le 10^5$) --- the number of elements in the array.
- Second line: $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$) --- the elements of the array, separated by spaces.
## Output Format
Output a single integer, which is the total count of all good subarrays.
## Sample Test Cases
### Sample Input 1
```
3
1 2 3
```
### Sample Output 1
```
4
```
### Sample Input 2
```
4
1 2 2 1
```
### Sample Output 2
```
7
```
## Constraints
- $1 \le n \le 10^5$
- $-10^9 \le a_i \le 10^9$
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
### Sample 1:
Given array $a = [1, 2, 3]$.
The subarrays are:
- $[1]$: Length $1$ (odd). Good.
- $[2]$: Length $1$ (odd). Good.
- $[3]$: Length $1$ (odd). Good.
- $[1, 2]$: Length $2$ (even). Sorted: $[1, 2]$. Middle elements are $b'_1=1, b'_2=2$. Since $1 \ne 2$, it is not good.
- $[2, 3]$: Length $2$ (even). Sorted: $[2, 3]$. Middle elements are $b'_1=2, b'_2=3$. Since $2 \ne 3$, it is not good.
- $[1, 2, 3]$: Length $3$ (odd). Good.
Total good subarrays: $3 + 0 + 0 + 1 = 4$.
### Sample 2:
Given array $a = [1, 2, 2, 1]$.
The good subarrays are:
- **Length 1 (all are good):** $[1], [2], [2], [1]$ (4 subarrays)
- **Length 2 (even):**
- $[1, 2]$: Sorted $[1, 2]$. Middle elements $b'_1=1, b'_2=2$. Not equal. Not good.
- $[2, 2]$: Sorted $[2, 2]$. Middle elements $b'_1=2, b'_2=2$. Equal. Good.
- $[2, 1]$: Sorted $[1, 2]$. Middle elements $b'_1=1, b'_2=2$. Not equal. Not good.
Total 1 good subarray of length 2.
- **Length 3 (all are good):** $[1, 2, 2], [2, 2, 1]$ (2 subarrays)
- **Length 4 (even):**
- $[1, 2, 2, 1]$: Sorted $[1, 1, 2, 2]$. Middle elements $b'_2=1, b'_3=2$. Not equal. Not good.
Total 0 good subarrays of length 4.
Total good subarrays: $4 + 1 + 2 + 0 = 7$.
Loading problem statement...