#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
const int MOD = 1e9 + 7;
const int N = 300010;
int a[N];
struct node
{
int len; ll cnt;
};
node st[2][N*4];
void combine(int type, int id)
{
int l = id*2; int r = (l^1);
if(st[type][l].len>st[type][r].len)
{
st[type][id] = st[type][l];
}
else if(st[type][l].len<st[type][r].len)
{
st[type][id] = st[type][r];
}
else
{
st[type][id] = st[type][l];
st[type][id].cnt = (st[type][r].cnt + st[type][id].cnt)%MOD;
}
}
int n;
void build(int type, int id = 1, int l = 0, int r = n)
{
if(r - l < 2)
{
st[type][id].len = -1;
st[type][id].cnt = 0;
return ;
}
int mid = (l+r)>>1;
build(type,id*2,l,mid);
build(type,id*2+1,mid,r);
combine(type, id);
}
void update(int type, int id, int l, int r, int pos, int mx, int cnt)
{
if(pos<l||pos>=r) return ;
if(r - l < 2)
{
st[type][id].cnt = cnt;
st[type][id].len = mx;
return ;
}
int mid = (l+r)>>1;
update(type,id*2,l,mid,pos,mx,cnt);
update(type,id*2+1,mid,r,pos,mx,cnt);
combine(type,id);
}
ii query(int type, int id, int l, int r, int ql, int qr)
{
if(qr<=l||r<=ql) return mp(-1, 0);
if(ql<=l&&r<=qr) return mp(st[type][id].len, st[type][id].cnt);
int mid = (l+r)>>1;
ii L = query(type,id*2, l, mid, ql, qr);
ii R = query(type,id*2+1, mid, r, ql, qr);
if(L.fi>R.fi) return L;
else if(L.fi<R.fi) return R;
else return (mp(L.fi, (L.se+R.se)%MOD));
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++)
{
cin>>a[i]; a[i]--;
}
build(0); build(1);
ll ans = 0; ll bestans = -1;
ll ans1 = 0; ll bestans1 = -1;
for(int i = 0; i < n; i++)
{
ii tmp1 = query(1, 1, 0, n, a[i] + 1, n + 1);
ii tmp0 = query(0, 1, 0, n, 0, a[i]);
if(tmp1.fi == -1)
{
tmp1 = mp(0, 1);
}
if(tmp0.fi == -1)
{
tmp0 = mp(0, 1);
}
if(tmp1.fi + 1 > bestans)
{
bestans = tmp1.fi + 1;
ans = tmp1.se;
}
else if(tmp1.fi + 1 == bestans)
{
ans = (ans + tmp1.se)%MOD;
}
if(tmp0.fi + 1 > bestans1)
{
bestans1 = tmp0.fi + 1;
ans1 = tmp0.se;
}
else if(tmp0.fi + 1 == bestans1)
{
ans1 = (ans1 + tmp0.se)%MOD;
}
update(1, 1, 0, n, a[i], tmp0.fi+1, tmp0.se);
update(0, 1, 0, n, a[i], tmp1.fi+1, tmp1.se);
}
if(bestans>bestans1)
{
cout << bestans << ' ' << ans << '\n';
}
else if(bestans<bestans1)
{
cout << bestans1 << ' ' << ans1 << '\n';
}
else
{
cout << bestans << ' ' << (ans+ans1)%MOD << '\n';
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdXNpbmcgbmFtZXNwYWNlIF9fZ251X3BiZHM7CiAKI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIHNlIHNlY29uZAojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGZibyBmaW5kX2J5X29yZGVyCiNkZWZpbmUgb29rIG9yZGVyX29mX2tleQogCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHBhaXI8aW50LGludD4gaWk7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgbG9uZyBkb3VibGUgbGQ7IAp0eXBlZGVmIHNldDxpbnQ+OjppdGVyYXRvciBzaXQ7CnR5cGVkZWYgbWFwPGludCxpbnQ+OjppdGVyYXRvciBtaXQ7CnR5cGVkZWYgdmVjdG9yPGludD46Oml0ZXJhdG9yIHZpdDsKIApjb25zdCBpbnQgTU9EID0gMWU5ICsgNzsKY29uc3QgaW50IE4gPSAzMDAwMTA7CiAKaW50IGFbTl07CiAKc3RydWN0IG5vZGUKewoJaW50IGxlbjsgbGwgY250Owp9OwogCm5vZGUgc3RbMl1bTio0XTsKIAp2b2lkIGNvbWJpbmUoaW50IHR5cGUsIGludCBpZCkKewoJaW50IGwgPSBpZCoyOyBpbnQgciA9IChsXjEpOwoJaWYoc3RbdHlwZV1bbF0ubGVuPnN0W3R5cGVdW3JdLmxlbikKCXsKCQlzdFt0eXBlXVtpZF0gPSBzdFt0eXBlXVtsXTsKCX0KCWVsc2UgaWYoc3RbdHlwZV1bbF0ubGVuPHN0W3R5cGVdW3JdLmxlbikKCXsKCQlzdFt0eXBlXVtpZF0gPSBzdFt0eXBlXVtyXTsKCX0KCWVsc2UKCXsKCQlzdFt0eXBlXVtpZF0gPSBzdFt0eXBlXVtsXTsKCQlzdFt0eXBlXVtpZF0uY250ID0gKHN0W3R5cGVdW3JdLmNudCArIHN0W3R5cGVdW2lkXS5jbnQpJU1PRDsKCX0KfQogCmludCBuOyAKIAp2b2lkIGJ1aWxkKGludCB0eXBlLCBpbnQgaWQgPSAxLCBpbnQgbCA9IDAsIGludCByID0gbikKewoJaWYociAtIGwgPCAyKQoJewoJCXN0W3R5cGVdW2lkXS5sZW4gPSAtMTsKCQlzdFt0eXBlXVtpZF0uY250ID0gMDsKCQlyZXR1cm4gOwoJfQoJaW50IG1pZCA9IChsK3IpPj4xOwoJYnVpbGQodHlwZSxpZCoyLGwsbWlkKTsKCWJ1aWxkKHR5cGUsaWQqMisxLG1pZCxyKTsKCWNvbWJpbmUodHlwZSwgaWQpOwp9CiAKdm9pZCB1cGRhdGUoaW50IHR5cGUsIGludCBpZCwgaW50IGwsIGludCByLCBpbnQgcG9zLCBpbnQgbXgsIGludCBjbnQpCnsJCglpZihwb3M8bHx8cG9zPj1yKSByZXR1cm4gOwoJaWYociAtIGwgPCAyKQoJewoJCXN0W3R5cGVdW2lkXS5jbnQgPSBjbnQ7CgkJc3RbdHlwZV1baWRdLmxlbiA9IG14OwoJCXJldHVybiA7Cgl9CglpbnQgbWlkID0gKGwrcik+PjE7Cgl1cGRhdGUodHlwZSxpZCoyLGwsbWlkLHBvcyxteCxjbnQpOwoJdXBkYXRlKHR5cGUsaWQqMisxLG1pZCxyLHBvcyxteCxjbnQpOwoJY29tYmluZSh0eXBlLGlkKTsKfQogCmlpIHF1ZXJ5KGludCB0eXBlLCBpbnQgaWQsIGludCBsLCBpbnQgciwgaW50IHFsLCBpbnQgcXIpCnsKCWlmKHFyPD1sfHxyPD1xbCkgcmV0dXJuIG1wKC0xLCAwKTsKCWlmKHFsPD1sJiZyPD1xcikgcmV0dXJuIG1wKHN0W3R5cGVdW2lkXS5sZW4sIHN0W3R5cGVdW2lkXS5jbnQpOwoJaW50IG1pZCA9IChsK3IpPj4xOwoJaWkgTCA9IHF1ZXJ5KHR5cGUsaWQqMiwgbCwgbWlkLCBxbCwgcXIpOwoJaWkgUiA9IHF1ZXJ5KHR5cGUsaWQqMisxLCBtaWQsIHIsIHFsLCBxcik7CglpZihMLmZpPlIuZmkpIHJldHVybiBMOwoJZWxzZSBpZihMLmZpPFIuZmkpIHJldHVybiBSOwoJZWxzZSByZXR1cm4gKG1wKEwuZmksIChMLnNlK1Iuc2UpJU1PRCkpOwp9CiAKaW50IG1haW4oKQp7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOyBjaW4udGllKDApOwoJY2luID4+IG47Cglmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQoJewoJCWNpbj4+YVtpXTsgYVtpXS0tOwoJfQoJYnVpbGQoMCk7IGJ1aWxkKDEpOwoJbGwgYW5zID0gMDsgbGwgYmVzdGFucyA9IC0xOwoJbGwgYW5zMSA9IDA7IGxsIGJlc3RhbnMxID0gLTE7Cglmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQoJewoJCWlpIHRtcDEgPSBxdWVyeSgxLCAxLCAwLCBuLCBhW2ldICsgMSwgbiArIDEpOwoJCWlpIHRtcDAgPSBxdWVyeSgwLCAxLCAwLCBuLCAwLCBhW2ldKTsKCQlpZih0bXAxLmZpID09IC0xKSAKCQl7CgkJCXRtcDEgPSBtcCgwLCAxKTsKCQl9CgkJaWYodG1wMC5maSA9PSAtMSkKCQl7CgkJCXRtcDAgPSBtcCgwLCAxKTsKCQl9CgkJaWYodG1wMS5maSArIDEgPiBiZXN0YW5zKQoJCXsKCQkJYmVzdGFucyA9IHRtcDEuZmkgKyAxOwoJCQlhbnMgPSB0bXAxLnNlOwoJCX0KCQllbHNlIGlmKHRtcDEuZmkgKyAxID09IGJlc3RhbnMpCgkJewoJCQlhbnMgPSAoYW5zICsgdG1wMS5zZSklTU9EOwoJCX0KCQlpZih0bXAwLmZpICsgMSA+IGJlc3RhbnMxKQoJCXsKCQkJYmVzdGFuczEgPSB0bXAwLmZpICsgMTsKCQkJYW5zMSA9IHRtcDAuc2U7CgkJfQoJCWVsc2UgaWYodG1wMC5maSArIDEgPT0gYmVzdGFuczEpCgkJewoJCQlhbnMxID0gKGFuczEgKyB0bXAwLnNlKSVNT0Q7CgkJfQoJCXVwZGF0ZSgxLCAxLCAwLCBuLCBhW2ldLCB0bXAwLmZpKzEsIHRtcDAuc2UpOwoJCXVwZGF0ZSgwLCAxLCAwLCBuLCBhW2ldLCB0bXAxLmZpKzEsIHRtcDEuc2UpOwoJfQoJaWYoYmVzdGFucz5iZXN0YW5zMSkKCXsKCQljb3V0IDw8IGJlc3RhbnMgPDwgJyAnIDw8IGFucyA8PCAnXG4nOwoJfQoJZWxzZSBpZihiZXN0YW5zPGJlc3RhbnMxKQoJewoJCWNvdXQgPDwgYmVzdGFuczEgPDwgJyAnIDw8IGFuczEgPDwgJ1xuJzsKCX0KCWVsc2UKCXsKCQljb3V0IDw8IGJlc3RhbnMgPDwgJyAnIDw8IChhbnMrYW5zMSklTU9EIDw8ICdcbic7Cgl9Cn0KIA==