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
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;

int STALA;
pair<int,int> drzewo[2100000];
pair<int,int> tab[1000100];
int n;
int find(int a, int b,int dlugosc)
{
    int moja_poz=drzewo[a-1+STALA].first;
    int prev_moja_poz=moja_poz;
    if (dlugosc%2==0)
        prev_moja_poz=drzewo[a-2+STALA].first;
    a+=STALA;
    b+=STALA;
    int wynik_max=-1;
    int wynik_min=1000000000;
   
    while (b>a)
    {
        if (a%2==1)
        {
            wynik_max=max(drzewo[a].second,wynik_max);
            wynik_min=min(drzewo[a].first,wynik_min);
            a++;
        }
        a/=2;
                        
        if (b%2==0)
        {
            wynik_max=max(drzewo[b].second,wynik_max);
            wynik_min=min(drzewo[b].first,wynik_min);
            b--;
        }
        b/=2;
    }
    if (a==b)
    {
        wynik_max=max(drzewo[a].second,wynik_max);
        wynik_min=min(drzewo[a].first,wynik_min);
    }
    
    //wynik_max - najdalszy na prawo ktorego musze wziac
    //cout<<"dlugosc: "<<dlugosc<<"\n";
    if (prev_moja_poz>moja_poz)
        swap(prev_moja_poz,moja_poz);
    //cout<<"moja_poz="<<moja_poz<<", wynik_min= "<<wynik_min<<", wynik_max="<<wynik_max<<"\n";
    
    if (moja_poz>wynik_max)
        wynik_max=moja_poz;
    if (wynik_min>prev_moja_poz)
        wynik_min=prev_moja_poz;
    if (wynik_min>wynik_max)
        swap(wynik_min,wynik_max);
    //cout<<"wynik_min= "<<wynik_min<<", wynik_max="<<wynik_max<<"\n";
    //wynik_min - najdalszy na lewo ktorego musze wziac
    int wynik=wynik_max-wynik_min+1; //tyle musimy juz wziac aby mediana sie zgadzala
    wynik=dlugosc-wynik; //tyle musimy dobrac elementow
    if (wynik<0)
    {
        //cout<<"wynik: "<<0<<"\n";
        return 1;
    }
    if (wynik==0)
    {
      //  cout<<"wynik: "<<1<<"\n";
        return 2;
    }
    int moge_z_lewej=wynik_min;
    int moge_z_prawej=n-wynik_max-1;
    //cout<<"tyle dobrac: "<<wynik<<", tyle moge z lewej: "<<moge_z_lewej<<",tyle moge z prawej: "<<moge_z_prawej<<"\n";
    if (moge_z_lewej+moge_z_prawej<wynik)
    {
        //cout<<"wynik: "<<0<<"\n";
        return 1;//o 1 wiecej zwracam (0)
    }
    if (moge_z_lewej+moge_z_prawej==wynik)
    {
       // cout<<"wynik: "<<1<<"\n";
        return 2;
    }
    
    //tu wynik<od miejsca
    if (moge_z_lewej>moge_z_prawej) swap(moge_z_lewej,moge_z_prawej);
    if (wynik==1)
    {
     //   cout<<"wynik: "<<min(moge_z_lewej,1)+min(moge_z_prawej,1)<<"\n";
        return min(moge_z_lewej,1)+min(moge_z_prawej,1)+1;
    }
    //wynik>1 wiec da sie go podzielic na dwie strony
    int out=moge_z_lewej+1; // z tylu miejsc conajwyzej moge zaczac, ale musze sprawedzic ktore z nich sie mieszcza ( wszystkie w lewej + pierwsze w prawej)
    out-=max(0,(wynik-moge_z_prawej));
    //odejmuje te ktore wystaja za prawa strone, albo nic jak nic nie wystaje
    out-=max(0,moge_z_lewej-wynik);
    //odejmuje te co nie dojda od lewej do srodka
   // cout<<"wynik: "<<out<<"\n";
    return out+1;
       
}
int main()
{
    int a;
    scanf("%d", &n);
    //wyznacz stala
    STALA=1;
    while (STALA<n)
    {
        STALA*=2;
    }
    for (int i=0; i<n; i++)
    {
        //cin>>a;
        scanf("%d", &a);
        tab[i]=make_pair(a,i);
    }
      
   // cout<<2*n+1<<" ";
    printf("%d ", 2*n+1);
    sort(tab,tab+n);

    for (int i=0; i<n; i++)
    {
        drzewo[(i+1)+STALA]=make_pair(tab[i].second,tab[i].second); //wart liczby+STALA
    }
    
    for (int i=2*STALA-1; i>1; i-=2)
    {
        drzewo[i/2]=make_pair(min(drzewo[i].first,drzewo[i-1].first),max(drzewo[i].second,drzewo[i-1].second));
    }
    
    long long wyn=0LL;
    
    for (int i=0; i<n; i++)
    {
        //cout<<i+1<<": ";
        //i+1 mediana - pozycja w drzewie to i
        int dlugosc=(2*n)+1-2*(i+1);
        if (!(dlugosc>n || dlugosc<=0))
            wyn+=(find(i+2,n,dlugosc)-1);
        // (i+1 + (i+2))/2 mediana
        dlugosc--;
        if (dlugosc>n || dlugosc<=0)
            continue;
        wyn+=(find(i+3,n,dlugosc)-1);
    }
    
    
   
    printf("%lld\n", wyn);
    //cout<<wyn<<"\n";
    
    return 0;
}