#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
#define int ll
vector<pair<int, int> > crit = {
{ 1, 2 },
{ 326, 4 },
{ 1608, 6 },
{ 5161, 8 },
{ 7228, 14 },
{ 21849, 16 },
{ 24564, 18 },
{ 29810, 20 },
{ 35985, 24 },
{ 38792, 26 },
{ 39055, 28 },
{ 41632, 32 },
{ 48472, 36 },
{ 49144, 38 },
{ 51772, 40 },
{ 60436, 42 },
{ 60886, 50 },
{ 61467, 52 },
{ 63619, 54 },
{ 70543, 56 },
{ 72187, 60 },
{ 72437, 62 },
{ 75024, 66 },
{ 76455, 68 },
{ 77220, 86 },
{ 86784, 92 },
{ 89046, 98 },
{ 91256, 104 },
{ 94768, 108 },
{ 95312, 112 },
{ 95915, 114 },
{ 96569, 130 },
{ 96626, 134 },
{ 99266, 140 },
{ 99723, 142 },
{ 100502, 196 },
{ 104253, 204 },
{ 107137, 252 },
{ 110618, 276 },
{ 111261, 280 },
{ 111608, 302 },
{ 112442, 306 },
{ 116957, 312 },
{ 116991, 322 },
{ 119613, 332 },
{ 120956, 370 },
{ 120977, 372 },
{ 121140, 388 },
{ 122561, 396 },
{ 123564, 400 },
{ 124067, 404 },
{ 124145, 414 },
{ 124461, 422 },
{ 124788, 444 },
{ 125020, 452 },
{ 125214, 458 },
{ 125396, 558 },
{ 126046, 564 },
{ 126302, 570 },
{ 126478, 574 },
{ 126579, 578 },
{ 126643, 584 },
{ 126766, 668 },
{ 127156, 670 },
{ 127162, 674 },
{ 128079, 682 },
{ 128131, 688 },
{ 129209, 690 },
{ 129421, 692 },
{ 129774, 712 },
{ 130308, 732 },
{ 130392, 744 },
{ 131202, 820 },
{ 131791, 822 },
{ 132070, 844 },
{ 132162, 846 },
{ 133226, 852 },
{ 133534, 880 },
{ 133671, 884 },
{ 134468, 922 },
{ 134483, 924 },
{ 134962, 944 },
{ 135083, 1050 },
{ 135219, 1180 },
{ 136017, 1302 },
{ 136177, 1432 },
{ 136344, 1534 },
{ 137144, 1704 },
{ 137923, 1808 },
{ 138662, 1976 },
{ 139071, 2104 },
{ 139831, 2214 },
{ 140110, 2406 },
{ 140622, 2544 },
{ 141443, 2648 },
{ 141471, 2906 },
{ 141688, 3230 },
{ 141859, 3374 },
{ 142036, 3816 },
{ 142140, 4000 },
{ 142659, 4124 },
{ 142925, 4228 },
{ 143069, 4330 },
{ 143194, 4436 },
{ 143580, 4584 },
{ 143776, 4830 },
{ 143964, 5546 },
{ 144205, 5652 },
{ 144268, 5806 },
{ 144369, 5936 },
{ 144408, 6534 },
{ 144877, 6848 },
{ 145153, 6974 },
{ 145382, 7764 },
{ 145455, 7880 },
{ 145609, 8212 },
{ 145884, 8470 },
{ 146009, 8664 },
{ 146137, 9200 },
{ 146167, 9318 },
{ 146350, 9434 },
{ 146409, 9536 },
{ 146472, 9648 },
{ 146515, 9832 },
{ 146521, 9940 },
{ 146546, 10224 },
{ 146602, 10346 },
{ 146645, 10674 },
{ 146917, 11300 },
{ 146922, 12142 },
{ 146948, 12332 },
{ 147085, 12436 },
{ 147118, 12544 },
{ 147150, 14806 },
{ 147164, 14996 },
{ 147226, 15536 },
{ 147287, 15726 },
{ 147458, 15852 },
{ 147541, 15956 },
{ 147558, 16328 },
{ 147619, 16466 },
{ 147697, 16574 },
{ 147708, 16932 },
{ 147727, 17220 },
{ 147765, 17344 },
{ 147776, 19902 },
{ 147851, 20670 },
{ 147897, 22320 },
{ 147981, 24212 },
{ 147994, 26418 },
{ 148031, 27066 },
{ 148040, 27380 },
{ 148046, 28152 },
{ 148069, 28530 },
{ 148101, 28800 },
{ 148114, 28922 },
{ 148141, 34578 },
{ 148158, 37242 },
{ 148173, 38010 },
{ 148215, 39736 },
{ 148231, 40504 },
{ 148270, 40618 },
{ 148276, 40728 },
{ 148287, 40892 },
{ 148315, 41010 },
{ 148331, 41246 },
{ 148361, 41348 },
{ 148368, 41486 },
{ 148379, 41634 },
{ 148419, 41760 },
{ 148430, 41984 },
{ 148444, 42106 },
{ 148445, 42458 },
{ 148477, 42568 },
{ 148493, 42674 },
{ 148510, 42846 },
{ 148524, 42954 },
{ 148608, 43082 },
{ 148648, 43194 },
{ 148688, 43330 },
{ 148706, 43770 },
{ 148712, 43890 },
{ 148713, 45854 },
{ 148720, 52516 },
{ 148753, 55010 },
{ 148760, 58850 },
{ 148794, 72542 },
{ 148801, 75036 },
{ 148812, 75166 },
{ 148814, 75684 },
{ 148816, 76600 },
{ 148822, 77048 },
{ 148833, 77154 },
{ 148836, 77272 },
{ 148843, 77436 },
{ 148853, 77538 },
{ 148869, 77744 },
{ 148872, 78256 },
{ 148875, 78398 },
{ 148886, 78536 },
{ 148891, 78644 },
{ 148910, 78840 },
{ 148932, 91980 },
{ 148937, 94472 },
{ 148939, 95462 },
{ 148948, 95650 },
{ 148962, 95856 },
{ 148965, 96926 },
{ 148971, 101628 },
{ 148972, 104122 },
{ 148981, 104224 },
{ 148982, 104350 },
{ 148983, 104510 },
{ 149003, 104638 },
{ 149013, 105006 },
{ 149016, 105962 },
{ 149037, 106070 },
{ 149049, 106188 },
{ 149055, 106350 },
{ 149072, 106478 },
{ 149089, 106702 },
{ 149090, 106866 },
{ 149104, 107592 },
{ 149106, 107696 },
{ 149113, 107834 },
{ 149114, 107980 },
{ 149126, 108088 },
{ 149132, 108232 },
{ 149138, 108354 },
{ 149150, 108508 },
{ 149152, 108776 },
{ 149162, 109836 },
{ 149174, 110076 },
{ 149188, 110182 },
{ 149190, 110288 },
{ 149192, 110464 },
{ 149198, 116996 },
{ 149203, 117124 },
{ 149205, 118616 },
{ 149214, 124830 },
{ 149218, 124936 },
{ 149223, 125054 },
{ 149224, 125218 },
{ 149249, 125330 },
{ 149261, 125442 },
{ 149270, 125544 },
{ 149297, 125734 },
{ 149314, 125942 },
{ 149339, 126588 },
{ 149351, 126690 },
{ 149354, 126868 },
{ 149358, 126980 },
{ 149370, 127102 },
{ 149397, 127220 },
{ 149405, 127418 },
{ 149409, 127520 },
{ 149422, 127622 },
{ 149423, 128016 },
{ 149442, 128124 },
{ 149448, 128262 },
{ 149462, 129274 },
{ 149472, 129584 },
{ 149478, 129730 },
{ 149485, 148992 },
{ 149488, 149176 },
{ 149497, 149284 },
{ 149508, 150832 },
{ 149516, 151014 },
{ 149529, 151122 },
{ 149530, 151348 },
{ 149534, 151528 },
{ 149539, 152472 },
{ 149545, 152660 },
{ 149550, 152768 },
{ 149551, 153368 },
{ 149560, 153648 },
{ 149564, 169700 },
{ 149571, 169880 },
{ 149580, 169998 },
{ 149596, 170120 },
{ 149605, 170228 },
{ 149607, 170338 },
{ 149613, 172236 },
{ 149622, 172516 },
{ 149628, 172656 },
{ 149647, 172764 },
{ 149653, 172880 },
{ 149659, 172990 },
{ 149663, 174150 },
{ 149669, 174264 },
{ 149671, 174492 },
{ 149673, 174624 },
{ 149681, 174728 },
{ 149683, 174860 },
{ 149684, 174998 },
{ 149698, 175302 },
{ 149709, 175452 },
{ 149715, 176592 },
{ 149718, 179306 },
{ 149720, 180382 },
{ 149727, 180530 },
{ 149734, 181202 },
{ 149736, 181682 },
{ 149742, 181794 },
{ 149751, 182290 },
{ 149755, 182444 },
{ 149758, 183562 },
{ 149759, 183752 },
{ 149763, 183928 },
{ 149772, 184034 },
{ 149779, 184148 },
{ 149786, 184794 },
{ 149791, 185164 },
{ 149797, 189974 },
{ 149798, 190280 },
{ 149803, 190486 },
{ 149806, 190836 },
{ 149813, 203660 },
{ 149818, 204030 },
{ 149828, 204152 },
{ 149830, 212648 },
{ 149842, 212766 },
{ 149845, 214486 },
{ 149855, 214826 },
{ 149858, 215000 },
{ 149860, 225568 },
{ 149863, 233352 },
{ 149876, 233498 },
{ 149880, 233610 },
{ 149886, 246274 },
{ 149890, 246492 },
{ 149896, 246598 },
{ 149904, 248334 },
{ 149907, 249190 },
{ 149908, 249536 },
{ 149910, 252206 },
{ 149912, 258450 },
{ 149918, 275916 },
{ 149922, 276268 },
{ 149929, 277754 },
{ 149932, 279158 },
{ 149937, 296620 },
{ 149941, 296976 },
{ 149948, 298040 },
{ 149957, 298152 },
{ 149961, 298276 },
{ 149968, 298490 },
{ 149970, 298600 },
{ 149971, 299510 },
{ 149978, 299638 },
{ 149984, 299742 },
{ 149991, 299864 },
{ 149998, 299992 },
{ 1000000, 300000},
};

mt19937 rng(time(0));

const int N = 3e5+100;
int n;
int p[N];
int q[N];

void gen(int k)
{
    n = k;
    for (int i=1; i<=n; i++)
        p[i] = i;
    shuffle(p+1, p+n+1, rng);

    cin>>n;
    for (int i=1; i<=n; i++)
        cin>>p[i];

    for (int i=1; i<=n; i++)
        q[p[i]] = i;
}

int big[N];
int cnt[2*N];
int mn[2*N];
int sum = 0;

int gans = 0;
int id = 0;
int curlen = 0;

double A = 1.1;
int L = 50;

void process(int val)
{
//    if (min(val, n+1-val) == crit[id].fi)
    while (min(val, n+1-val) >= crit[id].fi + n - 3e5)
        curlen = crit[id++].se;

    int pos = q[val];
    int len = curlen*A + L;
    int s = 0;
    for (int j=pos+1; j<=min(n+1, pos+len); j++)
    {
//        cout<<s<<" ";
        cnt[N+s]++;
        s += 2 * (p[j] > val) - 1;
    }
    int ans = 0;
    s = 0;
//    cout<<" : ";
    for (int j=pos-1; j>=max<int>(0, pos-len); j--)
    {
//        cout<<s<<" ";
        ans += cnt[N-s] + cnt[N-s+1];
        s += 2 * (p[j] > val) - 1;
    }
//    cout<<" -> "<<ans<<"\n";
    gans += ans*val;
    s = 0;
    for (int j=pos+1; j<=min(n+1, pos+len); j++)
    {
        cnt[N+s]--;
        s += 2 * (p[j] > val) - 1;
    }
//    cout<<val<<" "<<ans<<" "<<gans<<endl;
}
int solve(double a, int l)
{
    A = a;
    L = l;
    gans = 0;
    id = 0;
    for (int i=1; i<=n+1-i; i++)
    {
        process(i);
        if (i<n+1-i)
            process(n+1-i);
    }
    return gans;
}
int naive()
{
    int q = 0;
    for (int l=1; l<=n; l++)
        for (int r=l; r<=n; r++)
    {
        vector<int> v;
        for (int i=l; i<=r; i++)
            v.pb(p[i]);
        sort(v.begin(), v.end());
        q += v[(v.size()-1) / 2];
    }
    return q;
}

main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    gen(1000);
//    cout<<naive()<<endl;
    cout<<solve(3.5, 100)<<endl;
    return 0;

//    while (true)
//    {
//        gen(3e5);
//        int N = n*(n+1)/2;
//        cout<<solve(3.0, 50)<<endl;
//        cout<<solve(4.0, 50)<<endl;
//        cout<<solve(5.0, 50)<<endl;
//        cout<<solve(10.0, 50)<<endl;
//        cout<<endl;
//    }
//    return 0;

    int gans = 0;
    int gmx = 0;
    gen(3e5);
    for (int i=1; i<=n; i++)
    {
        int l = q[i];

        for (int i=0; i<2*N; i++)
            mn[i] = 1e9;
        int mxcur = 0;
        int s = 0;
        for (int j=1; j<=l; j++)
        {
            cnt[N+s]++;
            mn[N+s] = min(mn[N+s], j);
            s += 2 * (p[j] > i) - 1;
        }
        int ans = 0;
        for (int j=l+1; j<=n+1; j++)
        {
            if (mn[N+s] != int(1e9)) mxcur = max(mxcur, j-1-mn[N+s]+1);
            if (mn[N+s+1] != int(1e9)) mxcur = max(mxcur, j-1-mn[N+s+1]+1);

            ans += cnt[N+s] + cnt[N+s+1];
            s += 2 * (p[j] > i) - 1;
        }
        s = 0;
        for (int j=1; j<=l; j++)
        {
            cnt[N+s]--;
            s += 2 * (p[j] > i) - 1;
        }
        gans += ans * i;
//        cout<<i<<" "<<ans<<"\n";
        sum += mxcur;
        if (mxcur > gmx && (mxcur > gmx + 100 || mxcur < 1000))
        {
            cout<<"{ "<<i<<", "<<mxcur<<" },"<<endl;
            gmx = mxcur;
        }
    }
    cout<<gans<<"\n";
}

/*
1 2
66 4
3103 6
4988 10
15338 12
17352 14
25464 16
32798 18
35122 20
35457 22
40938 24
42994 30
46796 32
51452 34
53665 36
55852 40
61405 46
65272 50
68742 56
69144 68
74553 74
75466 78
76942 82
77287 86
80473 122
80554 126
83283 134
83477 138
83823 142
88234 154
89011 162
91814 172
95533 180
99803 196
100484 206
101534 222
102289 238
102632 242
104202 246
108262 252
109030 258
109529 262
111514 264
111771 274
112620 288
113149 304
113167 322
113693 328
114310 336
115348 344
115891 354
117162 372
118703 390
119034 442
119538 446
120870 464
121376 466
121414 488
121601 530
121749 588
121830 592
122172 610
123084 612
123226 634
123698 646
125932 688
126483 704
126639 708
126840 732
127074 774
127174 788
127758 796
128517 844
128708 866
129136 878
129419 888
129529 910
129697 912
129714 1126
132897 1228
134978 1352
136576 1456
136577 1594
137278 1700
138279 2106
139751 2238
140506 2382
141124 2494
141379 2622
141940 2732
142024 3040
142192 3172
142549 3438
142892 3556
143310 3668
143415 4496
143544 4642
143749 4972
144039 5116
144089 5230
144127 5382
144627 5496
144757 5864
144992 5974
145137 6368
145173 6560
145344 6674
145491 6790
145533 6908
145714 7064
146042 7186
146054 7446
146139 7604
146272 8042
146378 8198
146569 8806
146597 9526
146635 9922
146645 10024
146652 10240
146924 10352
146977 10482
147075 10598
147202 10794
147331 11504
147355 13818
147380 14158
147400 14320
147591 14436
147592 14574
147607 15670
147674 15786
147775 16012
147792 22322
147822 23042
147867 23294
147912 23410
147955 27382
147975 27526
148077 27642
148166 27772
148233 27906
148263 28022
148285 28228
148318 28344
148383 28714
148394 28832
148403 29372
148405 32200
148407 32920
148411 33164
148461 33416
148486 34122
148507 37260
148516 37504
148517 37648
148574 38462
148588 38606
148617 38808
148653 38918
148665 39020
148670 39122
148716 39254
148740 39368
148768 39510
148778 39620
148782 40640
148810 42338
148837 42550
148841 43208
148866 43316
148906 43838
148982 43954
149027 44264
149029 44418
149036 50518
149044 52258
149051 52502
149057 53086
149058 53460
149075 53630
149085 54288
149090 54396
149095 54592
149102 54918
149129 55120
149142 55230
149149 55350
149164 55498
149176 55688
149204 55810
149208 59968
149230 60084
149231 62434
149249 72218
149287 72666
149308 72782
149327 75162
149330 82098
149335 82340
149349 83300
149351 83496
149356 83610
149357 83746
149361 83952
149373 84058
149375 84168
149382 84282
149399 84412
149402 84514
149407 100110
149415 100226
149430 109988
149436 110232
149439 111190
149444 111392
149447 111502
149450 111706
149465 111810
149478 112004
149486 112146
149505 112256
149508 112418
149519 112544
149532 112682
149538 112796
149551 113198
149555 113394
149558 113500
149560 113696
149570 113810
149574 114016
149575 125522
149577 125642
149579 126118
149582 126398
149584 126518
149586 126866
149589 127508
149596 127642
149601 128508
149605 128872
149610 129108
149611 129384
149616 129916
149617 130496
149631 130872
149636 143306
149639 173572
149641 173716
149647 174174
149648 174448
149649 174592
149654 174980
149656 175564
149658 175704
149667 175806
149669 175950
149674 188570
149675 189398
149677 189528
149682 189998
149685 190274
149688 190806
149689 191386
149690 191490
149692 218408
149696 219004
149698 219284
149699 246300
149702 246408
149703 246900
149704 247176
149708 247708
149709 248290
149716 248424
149727 248730
149730 249336
149731 249528
149736 249798
149742 250234
149745 252094
149748 252388
149756 252492
149761 252736
149766 256742
149773 257354
149775 257516
149776 261446
149778 278708
149784 278814
149785 278934
149788 279198
149795 279374
149800 280048
149809 280166
149815 280396
149816 281718
149824 283494
149831 284856
149833 284988
149839 285106
149840 285214
149842 285460
149844 286200
149849 286314
149852 286426
149855 286690
149860 286958
149866 287082
149867 287538
149870 287868
149872 287998
149873 290638
149878 290746
149880 290852
149883 291116
149888 291236
149893 291372
149895 291988
149901 292096
149903 292222
149906 292486
149907 292692
149912 293650
149917 293756
149919 295426
149924 295532
149926 295838
149928 296000
149933 296106
149940 296232
149941 296776
149948 297188
149950 297350
149953 297478
149958 297662
149960 297892
149962 298052
149967 298236
149971 298564
149976 298864
149978 299248
149985 299664
149987 299822
149994 299950
*/