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
#include<bits/stdc++.h>

#define st first
#define nd second
#define pb(x) push_back(x)
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int MN=1e6+7;
int tab[MN];
int mini[MN];
int poz[MN];
int main()
{
    BOOST
    int n;
    cin>>n; int buf;
   for(int i=0; i<n; i++)
   {
       cin>>tab[i];
       poz[tab[i]]=i;
   }
   mini[poz[n]]=n;
   for(int i=poz[n]-1; i>-1; i--)
   {
       mini[i]=min(tab[i], mini[i+1]);
   }
   for(int i=poz[n]+1; i<n; i++)
   {
       mini[i]=min(tab[i], mini[i-1]);
   }
  // for(int i=0; i<n; i++) cout<<mini[i]<<' ';
  // cout<<"\n";
  // for(int i=0; i<n; i++) cout<<poz[i]<<' ';
    int l=poz[n]; int p=poz[n];
   set <pair <int, int> > zbior;
   //zbior.insert(cos)
   zbior.insert(mp(poz[n],poz[n]));
   int aktm,dl;
   //cout<<"\n";
   for(int i=n-1; i>0; i--)
   {
       l=min(l, poz[i]); p=max(p,poz[i]);
       aktm=min(mini[l], mini[p]);
       dl=n-p+l;
       //cout<<l<<' '<<p<<' '<<aktm<<' '<<n-p+l<<"\n";
       if(aktm==dl)
        {
            zbior.insert(mp(l,p));
            for(int j=1; j<dl/2+1; j++)
            {
                for(int k=0; k<j+1; k++)
                {if(l-k>=0 and p+j-k<n) zbior.insert(mp(l-k,p+j-k));}

            }
        }
   }
   cout<<2*n+1<<' '<<zbior.size();
   return 0 ;
}