1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;

    vector<int> numbers(n);
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        numbers[i] = a;
    }

    int left_iter = -1, right_iter = n;
    long long count = 0;
    for(int i=1; i<n; i++){
        int current_treshold = (n+i-1)/2;
        
        while(left_iter+1 < i && numbers[left_iter+1] <= current_treshold){
            ++left_iter;
        }
        
        while(right_iter-1 >= n-i && numbers[right_iter-1] <= current_treshold){
            --right_iter;
        }

        count += max(0, (left_iter+1) + (n-right_iter) + 1 - i);
    }

    cout << n*2+1 << " " << count+1 << "\n";
}