#include <iostream>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <math.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define sz(a) (int)a.size()
using namespace std;
inline void setmin(int &x, int y) { if (y < x) x = y; }
inline void setmax(int &x, int y) { if (y > x) x = y; }
inline void setmin(ll &x, ll y) { if (y < x) x = y; }
inline void setmax(ll &x, ll y) { if (y > x) x = y; }
const int N = 500000;
const int inf = (int)1e9 + 1;
const int MOD = (int)1e9 + 7;
const ld pi = atan2(0, -1);
int a[N];
int max_l[N], max_r[N];
void calc_max_to(int n)
{
int cur = -1, pos = 0;
deque<pair<int, int> > q;
for (int i = 0; i < n; i++)
{
while (sz(q) > 0 && a[i] <= q.back().fi)
q.pop_back();
q.push_back({a[i], i});
setmin(pos, sz(q) - 1);
while (cur + 1 <= i)
{
if (q[pos].se > cur)
{
if ((i - (cur + 1) + 1) >= q[pos].fi)
cur++;
else
break;
}
else
{
if (pos + 1 < sz(q) && (i - (cur + 1) + 1) >= q[pos + 1].fi)
{
cur++;
pos++;
}
else
break;
}
}
max_l[i] = cur;
}
}
int to_l[N], to_r[N];
int cnt_v;
int tree[1100000], add[1100000];
void build(int n)
{
cnt_v = 1;
while (cnt_v < n)
cnt_v <<= 1;
fill(tree, tree + cnt_v * 2 - 1, 0);
}
void push(int x, int lx, int rx)
{
if (add[x] == 0)
return;
int len = (rx - lx) >> 1;
tree[(x << 1) + 1] = (tree[(x << 1) + 1] + 1LL * add[x] * len) % MOD;
add[(x << 1) + 1] += add[x];
if (add[(x << 1) + 1] >= MOD)
add[(x << 1) + 1] -= MOD;
tree[(x << 1) + 2] = (tree[(x << 1) + 2] + 1LL * add[x] * len) % MOD;
add[(x << 1) + 2] += add[x];
if (add[(x << 1) + 2] >= MOD)
add[(x << 1) + 2] -= MOD;
add[x] = 0;
}
void upd(int x, int lx, int rx, int l, int r, int v)
{
if (lx >= r || l >= rx)
return;
else if (lx >= l && rx <= r)
{
tree[x] = (tree[x] + 1LL * v * (rx - lx)) % MOD;
add[x] += v;
if (add[x] >= MOD)
add[x] -= MOD;
}
else
{
push(x, lx, rx);
upd((x << 1) + 1, lx, (lx + rx) >> 1, l, r, v);
upd((x << 1) + 2, (lx + rx) >> 1, rx, l, r, v);
tree[x] = tree[(x << 1) + 1] + tree[(x << 1) + 2];
if (tree[x] >= MOD)
tree[x] -= MOD;
}
}
int get(int x, int lx, int rx, int l, int r)
{
if (lx >= r || l >= rx)
return 0;
else if (lx >= l && rx <= r)
return tree[x];
else
{
push(x, lx, rx);
int res = get((x << 1) + 1, lx, (lx + rx) >> 1, l, r) + get((x << 1) + 2, (lx + rx) >> 1, rx, l, r);
if (res >= MOD)
res -= MOD;
return res;
}
}
int main()
{
//freopen("a.in", "r", stdin);
//freopen("a.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.precision(20);
cout << fixed;
//ll TL = 0.95 * CLOCKS_PER_SEC;
//clock_t time = clock();
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
reverse(a, a + n);
calc_max_to(n);
for (int i = 0; i < n; i++)
max_r[i] = n - 1 - max_l[n - i - 1];
reverse(a, a + n);
calc_max_to(n);
/*for (int i = 0; i < n; i++)
cout << max_l[i] << " ";
cout << "\n";
for (int i = 0; i < n; i++)
cout << max_r[i] << " ";
cout << "\n";*/
vector<pair<int, int> > st;
st.push_back({inf, -1});
for (int i = 0; i < n; i++)
{
while (a[i] >= st.back().fi)
st.pop_back();
to_l[i] = st.back().se + 1;
st.push_back({a[i], i});
}
st.clear();
st.push_back({inf, n});
for (int i = n - 1; i >= 0; i--)
{
while (a[i] > st.back().fi)
st.pop_back();
to_r[i] = st.back().se - 1;
st.push_back({a[i], i});
}
/*cout << "\n";
for (int i = 0; i < n; i++)
cout << to_l[i] << " ";
cout << "\n";
for (int i = 0; i < n; i++)
cout << to_r[i] << " ";
cout << "\n";
cout << "\n";*/
int sum = 0;
for (int i = 0; i < n; i++)
sum += min(i - to_l[i] + 1, to_r[i] - i + 1);
assert(sum <= 3000000);
build(n);
for (int i = 0; i < n; i++)
if (to_r[i] - i <= i - to_l[i])
{
for (int j = i; j <= to_r[i]; j++)
{
int l = max(to_l[i], j - a[i] + 1), r = min(max_l[j], i);
if (l <= r)
{
int cnt = 0;
if (l == 0)
{
cnt++;
l++;
}
cnt += get(0, 0, cnt_v, l - 1, r);
if (cnt >= MOD)
cnt -= MOD;
upd(0, 0, cnt_v, j, j + 1, cnt);
}
}
}
else
{
for (int j = i; j >= to_l[i]; j--)
{
int l = max(i, max_r[j]), r = min(to_r[i], j + a[i] - 1);
if (l <= r)
{
int cnt = (j == 0 ? 1 : get(0, 0, cnt_v, j - 1, j));
upd(0, 0, cnt_v, l, r + 1, cnt);
}
}
}
/*for (int i = 0; i < n; i++)
cout << get(0, 0, cnt_v, i, i + 1) << " ";
cout << "\n";*/
cout << get(0, 0, cnt_v, n - 1, n) << "\n";
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RkbGliLmg+CiNpbmNsdWRlIDxjbWF0aD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGRlcXVlPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8YXNzZXJ0Lmg+CiNpbmNsdWRlIDxtYXRoLmg+CiAKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBsZCBsb25nIGRvdWJsZQojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgc3ooYSkgKGludClhLnNpemUoKQogCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKaW5saW5lIHZvaWQgc2V0bWluKGludCAmeCwgaW50IHkpIHsgaWYgKHkgPCB4KSB4ID0geTsgfQppbmxpbmUgdm9pZCBzZXRtYXgoaW50ICZ4LCBpbnQgeSkgeyBpZiAoeSA+IHgpIHggPSB5OyB9CmlubGluZSB2b2lkIHNldG1pbihsbCAmeCwgbGwgeSkgeyBpZiAoeSA8IHgpIHggPSB5OyB9CmlubGluZSB2b2lkIHNldG1heChsbCAmeCwgbGwgeSkgeyBpZiAoeSA+IHgpIHggPSB5OyB9CiAKY29uc3QgaW50IE4gPSA1MDAwMDA7CmNvbnN0IGludCBpbmYgPSAoaW50KTFlOSArIDE7CmNvbnN0IGludCBNT0QgPSAoaW50KTFlOSArIDc7CmNvbnN0IGxkIHBpID0gYXRhbjIoMCwgLTEpOwogCmludCBhW05dOwoKaW50IG1heF9sW05dLCBtYXhfcltOXTsKIAp2b2lkIGNhbGNfbWF4X3RvKGludCBuKQp7CiAgICBpbnQgY3VyID0gLTEsIHBvcyA9IDA7CiAgICBkZXF1ZTxwYWlyPGludCwgaW50PiA+IHE7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgIHsKICAgICAgICB3aGlsZSAoc3oocSkgPiAwICYmIGFbaV0gPD0gcS5iYWNrKCkuZmkpCiAgICAgICAgICAgIHEucG9wX2JhY2soKTsKICAgICAgICBxLnB1c2hfYmFjayh7YVtpXSwgaX0pOwogICAgICAgIHNldG1pbihwb3MsIHN6KHEpIC0gMSk7CiAgICAgICAgd2hpbGUgKGN1ciArIDEgPD0gaSkKICAgICAgICB7CiAgICAgICAgICAgIGlmIChxW3Bvc10uc2UgPiBjdXIpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmICgoaSAtIChjdXIgKyAxKSArIDEpID49IHFbcG9zXS5maSkKICAgICAgICAgICAgICAgICAgICBjdXIrKzsKICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmIChwb3MgKyAxIDwgc3oocSkgJiYgKGkgLSAoY3VyICsgMSkgKyAxKSA+PSBxW3BvcyArIDFdLmZpKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGN1cisrOwogICAgICAgICAgICAgICAgICAgIHBvcysrOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIG1heF9sW2ldID0gY3VyOwogICAgfQp9CgppbnQgdG9fbFtOXSwgdG9fcltOXTsKCmludCBjbnRfdjsKaW50IHRyZWVbMTEwMDAwMF0sIGFkZFsxMTAwMDAwXTsKCnZvaWQgYnVpbGQoaW50IG4pCnsKICAgIGNudF92ID0gMTsKICAgIHdoaWxlIChjbnRfdiA8IG4pCiAgICAgICAgY250X3YgPDw9IDE7CiAgICBmaWxsKHRyZWUsIHRyZWUgKyBjbnRfdiAqIDIgLSAxLCAwKTsKfQoKdm9pZCBwdXNoKGludCB4LCBpbnQgbHgsIGludCByeCkKewogICAgaWYgKGFkZFt4XSA9PSAwKQogICAgICAgIHJldHVybjsKICAgIGludCBsZW4gPSAocnggLSBseCkgPj4gMTsKICAgIHRyZWVbKHggPDwgMSkgKyAxXSA9ICh0cmVlWyh4IDw8IDEpICsgMV0gKyAxTEwgKiBhZGRbeF0gKiBsZW4pICUgTU9EOwogICAgYWRkWyh4IDw8IDEpICsgMV0gKz0gYWRkW3hdOwogICAgaWYgKGFkZFsoeCA8PCAxKSArIDFdID49IE1PRCkKICAgICAgICBhZGRbKHggPDwgMSkgKyAxXSAtPSBNT0Q7CiAgICB0cmVlWyh4IDw8IDEpICsgMl0gPSAodHJlZVsoeCA8PCAxKSArIDJdICsgMUxMICogYWRkW3hdICogbGVuKSAlIE1PRDsKICAgIGFkZFsoeCA8PCAxKSArIDJdICs9IGFkZFt4XTsKICAgIGlmIChhZGRbKHggPDwgMSkgKyAyXSA+PSBNT0QpCiAgICAgICAgYWRkWyh4IDw8IDEpICsgMl0gLT0gTU9EOwogICAgYWRkW3hdID0gMDsKfQoKdm9pZCB1cGQoaW50IHgsIGludCBseCwgaW50IHJ4LCBpbnQgbCwgaW50IHIsIGludCB2KQp7CiAgICBpZiAobHggPj0gciB8fCBsID49IHJ4KQogICAgICAgIHJldHVybjsKICAgIGVsc2UgaWYgKGx4ID49IGwgJiYgcnggPD0gcikKICAgIHsKICAgICAgICB0cmVlW3hdID0gKHRyZWVbeF0gKyAxTEwgKiB2ICogKHJ4IC0gbHgpKSAlIE1PRDsKICAgICAgICBhZGRbeF0gKz0gdjsKICAgICAgICBpZiAoYWRkW3hdID49IE1PRCkKICAgICAgICAgICAgYWRkW3hdIC09IE1PRDsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBwdXNoKHgsIGx4LCByeCk7CiAgICAgICAgdXBkKCh4IDw8IDEpICsgMSwgbHgsIChseCArIHJ4KSA+PiAxLCBsLCByLCB2KTsKICAgICAgICB1cGQoKHggPDwgMSkgKyAyLCAobHggKyByeCkgPj4gMSwgcngsIGwsIHIsIHYpOwogICAgICAgIHRyZWVbeF0gPSB0cmVlWyh4IDw8IDEpICsgMV0gKyB0cmVlWyh4IDw8IDEpICsgMl07CiAgICAgICAgaWYgKHRyZWVbeF0gPj0gTU9EKQogICAgICAgICAgICB0cmVlW3hdIC09IE1PRDsKICAgIH0KfQoKaW50IGdldChpbnQgeCwgaW50IGx4LCBpbnQgcngsIGludCBsLCBpbnQgcikKewogICAgaWYgKGx4ID49IHIgfHwgbCA+PSByeCkKICAgICAgICByZXR1cm4gMDsKICAgIGVsc2UgaWYgKGx4ID49IGwgJiYgcnggPD0gcikKICAgICAgICByZXR1cm4gdHJlZVt4XTsKICAgIGVsc2UKICAgIHsKICAgICAgICBwdXNoKHgsIGx4LCByeCk7CiAgICAgICAgaW50IHJlcyA9IGdldCgoeCA8PCAxKSArIDEsIGx4LCAobHggKyByeCkgPj4gMSwgbCwgcikgKyBnZXQoKHggPDwgMSkgKyAyLCAobHggKyByeCkgPj4gMSwgcngsIGwsIHIpOwogICAgICAgIGlmIChyZXMgPj0gTU9EKQogICAgICAgICAgICByZXMgLT0gTU9EOwogICAgICAgIHJldHVybiByZXM7CiAgICB9Cn0KCmludCBtYWluKCkKewogICAgLy9mcmVvcGVuKCJhLmluIiwgInIiLCBzdGRpbik7CiAgICAvL2ZyZW9wZW4oImEub3V0IiwgInciLCBzdGRvdXQpOwogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoMCk7CiAgICBjb3V0LnByZWNpc2lvbigyMCk7CiAgICBjb3V0IDw8IGZpeGVkOwogICAgLy9sbCBUTCA9IDAuOTUgKiBDTE9DS1NfUEVSX1NFQzsKICAgIC8vY2xvY2tfdCB0aW1lID0gY2xvY2soKTsKICAgIGludCBuOwogICAgY2luID4+IG47CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICBjaW4gPj4gYVtpXTsKCiAgICByZXZlcnNlKGEsIGEgKyBuKTsKICAgIGNhbGNfbWF4X3RvKG4pOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgICAgbWF4X3JbaV0gPSBuIC0gMSAtIG1heF9sW24gLSBpIC0gMV07CiAgICByZXZlcnNlKGEsIGEgKyBuKTsKICAgIGNhbGNfbWF4X3RvKG4pOwoKICAgIC8qZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgICAgY291dCA8PCBtYXhfbFtpXSA8PCAiICI7CiAgICBjb3V0IDw8ICJcbiI7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICBjb3V0IDw8IG1heF9yW2ldIDw8ICIgIjsKICAgIGNvdXQgPDwgIlxuIjsqLwoKICAgIHZlY3RvcjxwYWlyPGludCwgaW50PiA+IHN0OwogICAgc3QucHVzaF9iYWNrKHtpbmYsIC0xfSk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgIHsKICAgICAgICB3aGlsZSAoYVtpXSA+PSBzdC5iYWNrKCkuZmkpCiAgICAgICAgICAgIHN0LnBvcF9iYWNrKCk7CiAgICAgICAgdG9fbFtpXSA9IHN0LmJhY2soKS5zZSArIDE7CiAgICAgICAgc3QucHVzaF9iYWNrKHthW2ldLCBpfSk7CiAgICB9CiAgICBzdC5jbGVhcigpOwogICAgc3QucHVzaF9iYWNrKHtpbmYsIG59KTsKICAgIGZvciAoaW50IGkgPSBuIC0gMTsgaSA+PSAwOyBpLS0pCiAgICB7CiAgICAgICAgd2hpbGUgKGFbaV0gPiBzdC5iYWNrKCkuZmkpCiAgICAgICAgICAgIHN0LnBvcF9iYWNrKCk7CiAgICAgICAgdG9fcltpXSA9IHN0LmJhY2soKS5zZSAtIDE7CiAgICAgICAgc3QucHVzaF9iYWNrKHthW2ldLCBpfSk7CiAgICB9CgogICAgLypjb3V0IDw8ICJcbiI7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICBjb3V0IDw8IHRvX2xbaV0gPDwgIiAiOwogICAgY291dCA8PCAiXG4iOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgICAgY291dCA8PCB0b19yW2ldIDw8ICIgIjsKICAgIGNvdXQgPDwgIlxuIjsKICAgIGNvdXQgPDwgIlxuIjsqLwoKICAgIGludCBzdW0gPSAwOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgICAgc3VtICs9IG1pbihpIC0gdG9fbFtpXSArIDEsIHRvX3JbaV0gLSBpICsgMSk7CiAgICBhc3NlcnQoc3VtIDw9IDMwMDAwMDApOwoKICAgIGJ1aWxkKG4pOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgICAgaWYgKHRvX3JbaV0gLSBpIDw9IGkgLSB0b19sW2ldKQogICAgICAgIHsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IGk7IGogPD0gdG9fcltpXTsgaisrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpbnQgbCA9IG1heCh0b19sW2ldLCBqIC0gYVtpXSArIDEpLCByID0gbWluKG1heF9sW2pdLCBpKTsKICAgICAgICAgICAgICAgIGlmIChsIDw9IHIpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaW50IGNudCA9IDA7CiAgICAgICAgICAgICAgICAgICAgaWYgKGwgPT0gMCkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGNudCsrOwogICAgICAgICAgICAgICAgICAgICAgICBsKys7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGNudCArPSBnZXQoMCwgMCwgY250X3YsIGwgLSAxLCByKTsKICAgICAgICAgICAgICAgICAgICBpZiAoY250ID49IE1PRCkKICAgICAgICAgICAgICAgICAgICAgICAgY250IC09IE1PRDsKICAgICAgICAgICAgICAgICAgICB1cGQoMCwgMCwgY250X3YsIGosIGogKyAxLCBjbnQpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGZvciAoaW50IGogPSBpOyBqID49IHRvX2xbaV07IGotLSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IGwgPSBtYXgoaSwgbWF4X3Jbal0pLCByID0gbWluKHRvX3JbaV0sIGogKyBhW2ldIC0gMSk7CiAgICAgICAgICAgICAgICBpZiAobCA8PSByKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGludCBjbnQgPSAoaiA9PSAwID8gMSA6IGdldCgwLCAwLCBjbnRfdiwgaiAtIDEsIGopKTsKICAgICAgICAgICAgICAgICAgICB1cGQoMCwgMCwgY250X3YsIGwsIHIgKyAxLCBjbnQpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgLypmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICBjb3V0IDw8IGdldCgwLCAwLCBjbnRfdiwgaSwgaSArIDEpIDw8ICIgIjsKICAgIGNvdXQgPDwgIlxuIjsqLwogICAgY291dCA8PCBnZXQoMCwgMCwgY250X3YsIG4gLSAxLCBuKSA8PCAiXG4iOwogICAgcmV0dXJuIDA7Cn0=