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
/*  Potyczki Algorytmiczne 2021 Runda 4 A Ranking sklepów internetowych (RAN)
    tsz
*/
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <memory.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

#include <algorithm>

#ifndef TSDEBUG
#define NDEBUG 1
#endif

#ifdef __MINGW32__
#define FMTU64 "I64u"
#define FMTI64 "I64d"
#else
#define FMTU64 "llu"
#define FMTI64 "lld"
#endif 

typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;

typedef uint64_t u64;

inline i32 Min(i32 a, i32 b)
{
    return a <= b ? a : b;
}

inline i32 Max(i32 a, i32 b)
{
    return a >= b ? a : b;
}

const i32 MinLiczbaOcen = 1;
const i32 MaxLiczbaOcen = 1000000;

i32 Pozycje[MaxLiczbaOcen + 1] = {0};

int main()
{
    i32 LiczbaOcen = 0;
    scanf("%d\n", &LiczbaOcen);
    assert(MinLiczbaOcen <= LiczbaOcen);
    assert(LiczbaOcen <= MaxLiczbaOcen);

    if (LiczbaOcen == 1) {
        printf("3 1\n");
        return 0;
    }

    for (i32 i = 1; i <= LiczbaOcen; i++) {
        i32 Ocena;
        scanf("%d", &Ocena);
        assert(1 <= Ocena);
        assert(Ocena <= LiczbaOcen);
        assert(Pozycje[Ocena] == 0);
        Pozycje[Ocena] = i;
    }

    i32 Cel = 2 * LiczbaOcen + 1;
    i64 LiczbaSposobow = 2;

    i32 Left = Pozycje[LiczbaOcen];
    i32 Right = Left;

    i32 K = LiczbaOcen - 1;
    i32 SzukanaDlugosc = 2;
    for (;;) {
        if (SzukanaDlugosc == LiczbaOcen) break;
        i32 NowaPozycja = Pozycje[K];
        if (NowaPozycja < Left) {
            Left = NowaPozycja;
        } else if (NowaPozycja > Right) {
            Right = NowaPozycja;
        }
        i32 Dlugosc = Right - Left + 1;
        if (Dlugosc <= SzukanaDlugosc) {
            i32 a = Max(Left - SzukanaDlugosc + Dlugosc, 1);
            i32 b = Min(Left, LiczbaOcen - SzukanaDlugosc + 1);
            LiczbaSposobow += b - a + 1;
        }
        SzukanaDlugosc++;
        if (SzukanaDlugosc == LiczbaOcen) break;
        if (Dlugosc <= SzukanaDlugosc) {
            i32 a = Max(Left - SzukanaDlugosc + Dlugosc, 1);
            i32 b = Min(Left, LiczbaOcen - SzukanaDlugosc + 1);
            LiczbaSposobow += b - a + 1;
        }
        SzukanaDlugosc++;
        K--;
    }

    printf("%d %" FMTI64 "\n", Cel, LiczbaSposobow);

    return 0;
}