// #pragma GCC optimize ("Ofast") // #pragma GCC target ("avx,avx2") // #pragma GCC optimize("unroll-loops") #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> #define ll long long #define ld long double #define pl pair<ll, ll> #define vi vector<ll> #define vii vector<vi> #define vc vector<char> #define vcc vector<vc> #define vp vector<pl> #define mi map<ll,ll> #define mc map<char,int> #define sortx(X) sort(X.begin(),X.end()); #define all(X) X.begin(),X.end() #define allr(X) X.rbegin(),X.rend() #define ln '\n' #define YES {cout << "YES\n"; return;} #define NO {cout << "NO\n"; return;} #define MUN {cout << "0\n"; return;} const int MODE = 1e9+7; using namespace std; struct iteam { ll sz, cnt, one; iteam(){sz=cnt=one=0;} iteam(ll a, ll b,ll c){sz=a,cnt=b,one=c;} }; iteam mrg(iteam &a, iteam&b) { if (a.sz > b.sz) return a; if (a.sz < b.sz) return b; iteam ret = a; ret.cnt = (a.cnt+b.cnt)%MODE; ret.one = (a.one+b.one)%MODE; return ret; } struct segmax { int sgsize; vector<iteam> sgtree; const iteam neutral = iteam(); segmax(ll n) { n+=5; sgsize = n; sgtree.assign(sgsize*4, neutral); } void update(int idx, iteam val) { idx += sgsize; sgtree[idx] = mrg(sgtree[idx], val); for (idx /= 2; idx; idx /= 2) sgtree[idx] = mrg(sgtree[2 * idx], sgtree[2 * idx + 1]); } iteam query(int lo, int hi) { iteam ra, rb; ra = rb = neutral; for (lo += sgsize, hi += sgsize + 1; lo < hi; lo /= 2, hi /= 2) { if (lo & 1) ra = mrg(ra, sgtree[lo++]); if (hi & 1) rb = mrg(rb, sgtree[--hi]); } return mrg(ra, rb); } void clear() { sgtree.assign(sgsize*4, neutral); } }; void solve(int tc) { ll n; cin >> n; vi X(n); for (int i = 0; i < n; i++) { cin >> X[i]; } vi VC(X); sortx(VC); VC.erase(unique(all(VC)), VC.end()); auto get = [&](ll v) { return lower_bound(all(VC), v) - VC.begin(); }; for (auto &a : X) a = get(a); segmax sg(n); vector<iteam> dpr(n); sg.update(n, iteam(0, 1, 0)); for (int i = n - 1; i >= 0; i--) { dpr[i] = sg.query(X[i]+1, n); dpr[i].sz++; if (!i) swap(dpr[i].cnt, dpr[i].one); sg.update(X[i], dpr[i]); } sg.clear(); // segmax sg(n); vector<iteam> dp(n); for (int i = 0; i < n; i++) { iteam &v = dp[i]; v = dpr[i]; iteam re = sg.query(X[i]+1, n); re.sz++; v = mrg(v, re); sg.update(X[i], v); } ll mx = 0; for (int i = 0; i < n; i++) { mx = max(mx, dp[i].sz); } vi pw(n+1, 1); for (int i = 1; i <= n; i++) { pw[i] = (2 * pw[i-1]) % MODE; } ll l = n - mx; ll cnt = 0; if (dp[0].sz == mx) { cnt = (dp[0].one * pw[l]) % MODE; } for (int i = 1; i < n; i++) { if (dp[i].sz != mx) continue; ll re = 0; if (dpr[i].sz == mx) { dp[i].cnt -= dpr[i].cnt; dp[i].cnt = (dp[i].cnt%MODE+MODE)%MODE; re += (dpr[i].cnt * pw[l]) % MODE; re %= MODE; } re += (dp[i].one * pw[l]) % MODE; re %= MODE; if (l) { re += (dp[i].cnt * pw[l]) % MODE; re %= MODE; } // only next // 2^{l} * cnt // prv // withone: 2^l * cnt // without: 2^{l-1}*cnt1 cnt = (cnt + re) % MODE; } cout << mx << ' ' << cnt << '\n'; } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int size = 1; //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); // cin >> size; for (int i = 1; i <= size; i++) solve(i); }