//#define USEPB_DS
#define USETR1
#define CPPELEVEN
#define GPP

/*
 * temp.cpp
 *
 *  Created on: 2012-7-18
 *      Author: BSBandme
 */
//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <iostream>
#include <fstream>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cassert>
#include <list>
#include <iomanip>
#include <math.h>
#include <deque>
#include <utility>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <climits>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <sstream>
#include <tuple>

using namespace std;

#ifndef CPPELEVEN
#ifdef USETR1
#include <tr1/unordered_map>
#include <tr1/unordered_set>
using namespace tr1;
#endif
#else
#include <unordered_map>
#include <unordered_set>
#endif

#ifdef USEPB_DS
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
// binomial_heap_tag, rc_binomial_heap_tag, thin_heap_tag, binary_heap_tag
typedef __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> pq_type;
// splay_tree_tag, ov_tree_tag
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> tree_type;
#endif

#define mpr make_pair
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <double, double> pdd;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <double> vd;
typedef vector <string> vs;
typedef map <string, int> mpsi;
typedef map <double, int> mpdi;
typedef map <int, int> mpii;

const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};

template <class T> inline T abs1(T a) {return a < 0 ? -a : a;}

#ifndef CPPELEVEN
template <class T> inline T max1(T a, T b) { return b < a ? a : b; }
template <class T> inline T max1(T a, T b, T c) { return max1(max1(a, b), c); }
template <class T> inline T max1(T a, T b, T c, T d) { return max1(max1(a, b, c), d); }
template <class T> inline T max1(T a, T b, T c, T d, T e) { return max1(max1(a, b, c, d), e); }
template <class T> inline T min1(T a, T b) { return a < b ? a : b; }
template <class T> inline T min1(T a, T b, T c) { return min1(min1(a, b), c); }
template <class T> inline T min1(T a, T b, T c, T d) { return min1(min1(a, b, c), d); }
template <class T> inline T min1(T a, T b, T c, T d, T e) { return min1(min1(a, b, c, d), e); }
#else
template <typename t, typename t1>
t min1(t a, t1 b) { return a < b ? a : b; }
template <typename t, typename... arg>
t min1(t a, arg... arr) { return min1(a, min1(arr...)); }
template <typename t, typename t1>
t max1(t a, t1 b) { return a > b ? a : b; }
template <typename t, typename... arg>
t max1(t a, arg... arr) { return max1(a, max1(arr...)); }
#endif

inline int jud(double a, double b){
	if(abs(a) < eps && abs(b) < eps) return 0;
	else if(abs1(a - b) / max(abs1(a), abs1(b)) < eps) return 0;
	if(a < b) return -1;
	return 1;
}
template <typename t> inline int jud(t a, t b){
	if(a < b) return -1;
	if(a == b) return 0;
	return 1;
}

// f_lb == 1代表返回相同的一串的左边界，f_small == 1代表返回如果没有寻找的值返回小的数
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1){
	if(na == 0) return 0;
	int be = 0, en = na - 1;
	if(*a <= *(a + na - 1)){
		if(f_lb == 0) while(be < en){
			int mid = (be + en + 1) / 2;
			if(jud(*(a + mid), val) != 1) be = mid;
			else en = mid - 1;
		}else while(be < en){
			int mid = (be + en) / 2;
			if(jud(*(a + mid), val) != -1) en = mid;
			else be = mid + 1;
		}
		if(f_small && jud(*(a + be), val) == 1) be--;
		if(!f_small && jud(*(a + be), val) == -1) be++;
	} else {
		if(f_lb) while(be < en){
			int mid = (be + en + 1) / 2;
			if(jud(*(a + mid), val) != -1) be = mid;
			else en = mid - 1;
		}else while(be < en){
			int mid = (be + en) / 2;
			if(jud(*(a + mid), val) != 1) en = mid;
			else be = mid + 1;
		}
		if(!f_small && jud(*(a + be), val) == -1) be--;
		if(f_small && jud(*(a + be), val) == 1) be++;
	}
	return be;
}

template <class T> inline T lowb(T num) {return num & (-num); }
#ifdef GPP
inline int bitnum(ui nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(ull nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitnum(ll nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitmaxl(ui a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(int a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(ull a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
inline int bitmaxl(ll a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
#else
#endif

long long pow(long long n, long long m, long long mod = 0){
	if(m < 0) return 0;
	long long ans = 1;
	long long k = n;
	while(m){
		if(m & 1) {
			ans *= k;
			if(mod) ans %= mod;
		}
		k *= k;
		if(mod) k %= mod;
		m >>= 1;
	}
	return ans;
}

#define  MOD 1000000007
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
	if(mod == -1) mod = MOD;
	a += b;
	while(a >= mod) a -= mod;
	while(a < 0) a += mod;
}
template <class t>
void output1(t arr) {
	for(int i = 0; i < (int)arr.size(); i++)
		cerr << arr[i] << ' ';
	cerr << endl;
}
template <class t>
void output2(t arr) {
	for(int i = 0; i < (int)arr.size(); i++)
		output1(arr[i]);
}

//....................密..........封..........线..........下..........禁..........止..........hack...............................................

const int mod = MOD;
template <typename t> struct matrix{
	const static int maxn = 3;
	int row, col;
	t mat[maxn][maxn];

	matrix(int r = 0, int c = 0){
		row = r; col = c;
		for(int i = 0; i < row; i++) for(int j = 0; j < col; j++) mat[i][j] = 0;
	}
	const t * operator[] (int i) const {
		return mat[i];
	}
	t * operator[] (int i) {
		return mat[i];
	}
	bool danweiju(){
		if(row != col) return 0;
		for(int i = 0; i < row; i++) for(int j = 0; j < col; j++) mat[i][j] = bool (i == j);
		return 1;
	}
	matrix operator * (const matrix& b) const{
		int i, j, k;
		matrix <t> c(row, b.col);
		memset(c.mat, 0, sizeof(c.mat));
		for (i = 0; i < c.row; i++) for (k = 0; k < col; k++)
			if(mat[i][k])
				for (j = 0; j < c.col; j++){
					c.mat[i][j] += mat[i][k] * b.mat[k][j];
					c.mat[i][j] %= mod;
				}
		return c;
	}
	matrix operator + (const matrix& b) const{
		matrix <t> c(max1(row, b.row), max1(col, b.col));
		for(int i = 0; i < c.row; i++) for(int j = 0; j < c.col; j++){
			t a = 0; if(i < row && j < col) a = mat[i][j];
			t b1 = 0; if(i < b.row && j < b.col) b1 = b.mat[i][j];
			c.mat[i][j] = a + b1;
			c.mat[i][j] %= mod;
		}
		return c;
	}
	matrix operator - (const matrix& b) const{
		matrix <t> c(max1(row, b.row), max1(col, b.col));
		for(int i = 0; i < c.row; i++) for(int j = 0; j < c.col; j++){
			t a = 0; if(i < row && j < col) a = mat[i][j];
			t b1 = 0; if(i < b.row && j < b.col) b1 = b.mat[i][j];
			c.mat[i][j] = a - b1;
		}
		return c;
	}
	inline void operator = (const matrix & b){
		memcpy(mat, b.mat, sizeof(mat));
		col = b.col;  row = b.row;
	}
	matrix pow(long long n){
		matrix <t> ans(row, col), temp = *this;

		ans.danweiju();
		while(n){
			if(n & 1) ans = ans * temp;
			temp = temp * temp;
			n >>= 1;
		}
		return ans;
	}
	matrix addpow(long long n) {// calculate 1 + m + m ^ 2 + ... + m ^ n
		n++;
		matrix <t> ans(row, col), temp = *this, temp1(row, col), ans1(row, col);

		ans.danweiju(); temp1.danweiju();
		while(n){
			if(n & 1){
				ans1 = ans1 + ans * temp1;
				temp1 = temp * temp1;
			}
			ans = ans + ans * temp;
			temp = temp * temp;
			n >>= 1;
		}
		return ans1;
	}
	int inv(){
		int i, j, k, is[maxn], js[maxn];
		double t1;

		if (row != col) return 0;
		for(k = 0; k < row; k++){
			for(t1 = 0,i = k; i < row; i++) for(j = k; j < row; j++)
				if(fabs(mat[i][j]) > t1)
					t1=fabs(mat[is[k] = i][js[k] = j]);
			if (fabs(t1 - 0) < 1e-9) return 0;
			if (is[k] != k) for(j = 0; j < row; j++)
				t1 = mat[k][j], mat[k][j] = mat[is[k]][j], mat[is[k]][j] = t1;
			if (js[k] != k) for (i = 0; i < row; i++)
				t1 = mat[i][k], mat[i][k] = mat[i][js[k]], mat[i][js[k]] = t1;
			mat[k][k] = 1 / mat[k][k];
			for(j = 0; j < row; j++) if (j != k)
				mat[k][j] *= mat[k][k];
			for (i = 0; i < row; i++)	if (i != k)
				for (j = 0; j < row; j++) if (j != k)
					mat[i][j] -= mat[i][k] * mat[k][j];
			for (i = 0;i < row; i++) if (i != k)
				mat[i][k] *= -mat[k][k];
		}
		for (k = row-1; k >= 0; k--){
			for (j = 0; j < row; j++) if (js[k] != k)
					t1 = mat[k][j], mat[k][j] = mat[js[k]][j], mat[js[k]][j]=t1;
			for (i = 0; i < row; i++) if (is[k] != k)
				t1 = mat[i][k], mat[i][k] = mat[i][is[k]], mat[i][is[k]] = t1;
		}
		return 1;
	}
	double det(){
		int i, j, k, sign = 0;
		double b[maxn][maxn], ret = 1, t1;

		if (row != col) return 0;
		for (i = 0; i < row; i++) for (j = 0; j < col; j++)
			b[i][j] = mat[i][j];
		for (i = 0; i < row; i++){
			if (fabs(b[i][i] - 0) < 1e-9){
				for (j = i + 1; j < row; j++)
					if (fabs(b[j][i] - 0) > 1e-9) break;
					if (j == row) return 0;
					for (k = i; k < row; k++)
						t1 = b[i][k], b[i][k] = b[j][k], b[j][k] = t1;
					sign++;
			}
			ret *= b[i][i];
			for (k = i + 1; k < row; k++) b[i][k] /= b[i][i];
			for (j = i + 1; j < row; j++) for (k = i + 1; k < row; k++)
				b[j][k] -= b[j][i] * b[i][k];
		}
		if (sign & 1) ret = -ret;
		return ret;
	}
};

#ifndef N
#define N 200100
#endif
struct segment_node{
	int be, en, to_n;
	pll all_prob_sum, already_set_after_sum, minus_set_after_sum; // first: haven't, second have
	ll sum;
	matrix<ll> add_h, add_ht;
 };
struct segment_tree{
	int l;
	segment_node tree[N * 4];

	inline int gleft(int no) {return no << 1;}
	inline int gright(int no) {return (no << 1) + 1;}
	inline int gfa(int no) {return no >> 1;}
	inline segment_tree(){ l = 0; }

	void build(int no, int l, int r, int n){
		if(l > r) r = l;
		tree[no].add_h.row = tree[no].add_h.col = 3;
		tree[no].add_h.danweiju();
		tree[no].add_ht = tree[no].add_h;
		tree[no].to_n = n - r - 1;
		tree[no].sum = 0;
		if(l == r) {
			tree[no].be = tree[no].en = l;
			tree[no].all_prob_sum = mpr(1, 0);
			tree[no].already_set_after_sum = mpr(0, 0);
			tree[no].minus_set_after_sum = mpr(0, 0);
			return;
		} else {
			int mid = (l + r) / 2;
			build(gleft(no), l, mid, n);
			build(gright(no), mid + 1, r, n);
			tree[no].be = l; tree[no].en = r;
			push_up(no);
		}
	}
	inline void push_up(int no) {
		int le = gleft(no), ri = gright(no);
		tree[no].all_prob_sum = mpr(0, 0);
		tree[no].already_set_after_sum = mpr(0, 0);
		tree[no].minus_set_after_sum = mpr(0, 0);
		add(tree[no].all_prob_sum.first, tree[le].all_prob_sum.first);
		add(tree[no].all_prob_sum.second, tree[le].all_prob_sum.second);
		add(tree[no].already_set_after_sum.first, tree[le].already_set_after_sum.first);
		add(tree[no].already_set_after_sum.second, tree[le].already_set_after_sum.second);
		add(tree[no].minus_set_after_sum.first, tree[le].minus_set_after_sum.first);
		add(tree[no].minus_set_after_sum.second, tree[le].minus_set_after_sum.second);
		add(tree[no].all_prob_sum.first, tree[ri].all_prob_sum.first);
		add(tree[no].all_prob_sum.second, tree[ri].all_prob_sum.second);
		add(tree[no].already_set_after_sum.first, tree[ri].already_set_after_sum.first);
		add(tree[no].already_set_after_sum.second, tree[ri].already_set_after_sum.second);
		add(tree[no].minus_set_after_sum.first, tree[ri].minus_set_after_sum.first);
		add(tree[no].minus_set_after_sum.second, tree[ri].minus_set_after_sum.second);
		tree[no].sum = tree[le].sum + tree[ri].sum;
		tree[no].sum %= mod;
		tree[no].add_h.danweiju();
		tree[no].add_ht.danweiju();
	}
	inline void mul(ll &a, ll &b, ll &c, const matrix<ll> &m) {
		ll ra = m[0][0] * a + m[1][0] * b + m[2][0] * c;
		ll rb = m[0][1] * a + m[1][1] * b + m[2][1] * c;
		ll rc = m[0][2] * a + m[1][2] * b + m[2][2] * c;
		a = ra % mod;
		b = rb % mod;
		c = rc % mod;
	}
	inline void push_down(int no) {
		int le = gleft(no), ri = gright(no);
		tree[le].add_h = tree[le].add_h * tree[no].add_h;
		tree[le].add_ht = tree[le].add_ht * tree[no].add_ht;
		mul(tree[le].all_prob_sum.first, tree[le].already_set_after_sum.first, tree[le].minus_set_after_sum.first, tree[no].add_ht);
		mul(tree[le].all_prob_sum.second, tree[le].already_set_after_sum.second, tree[le].minus_set_after_sum.second, tree[no].add_h);
		tree[le].sum *= tree[no].add_h[0][0];
		tree[le].sum %= mod;
		tree[ri].add_h = tree[ri].add_h * tree[no].add_h;
		tree[ri].add_ht = tree[ri].add_ht * tree[no].add_ht;
		mul(tree[ri].all_prob_sum.first, tree[ri].already_set_after_sum.first, tree[ri].minus_set_after_sum.first, tree[no].add_ht);
		mul(tree[ri].all_prob_sum.second, tree[ri].already_set_after_sum.second, tree[ri].minus_set_after_sum.second, tree[no].add_h);
		tree[ri].sum *= tree[no].add_h[0][0];
		tree[ri].sum %= mod;
		tree[no].add_h.danweiju();
		tree[no].add_ht.danweiju();
	}
	void upd(int l, int r, int no, const matrix<ll>& rm_have, const matrix<ll> &rm_havent) {
		if(l <= tree[no].be && r >= tree[no].en){
			tree[no].add_h = tree[no].add_h * rm_have;
			tree[no].add_ht = tree[no].add_ht * rm_havent;
			mul(tree[no].all_prob_sum.first, tree[no].already_set_after_sum.first, tree[no].minus_set_after_sum.first, rm_havent);
			mul(tree[no].all_prob_sum.second, tree[no].already_set_after_sum.second, tree[no].minus_set_after_sum.second, rm_have);
			tree[no].sum *= rm_have[0][0];
			tree[no].sum %= mod;
			return;
		}
		push_down(no);
		int mid = (tree[no].be + tree[no].en) >> 1;
		if(r >= tree[no].be && l <= mid) upd(l, r, gleft(no), rm_have, rm_havent);
		if(r >= mid + 1 && l <= tree[no].en) upd(l, r, gright(no), rm_have, rm_havent);
		push_up(no);
	}
	void upd(int loc, int no) {
		if(tree[no].be == tree[no].en){
			add(tree[no].all_prob_sum.second, tree[no].all_prob_sum.first);
			add(tree[no].already_set_after_sum.second, tree[no].already_set_after_sum.first);
			add(tree[no].minus_set_after_sum.second, tree[no].minus_set_after_sum.first);
			tree[no].all_prob_sum.first = tree[no].already_set_after_sum.first = tree[no].minus_set_after_sum.first = 0;
			tree[no].sum = tree[no].all_prob_sum.second * tree[no].to_n % mod;
			return;
		}
		push_down(no);
		int mid = (tree[no].be + tree[no].en) >> 1;
		if(loc <= mid) upd(loc, gleft(no));
		else upd(loc, gright(no));
		push_up(no);
	}
} g;

const int maxn = N;

int n;
pii arr[maxn];


int main() {


//............................不要再忘了检查maxn大小了！！！！BSBandme你个SB！！！！...................................................

	ios_base::sync_with_stdio(0);
	#ifdef DEBUG //......................................................................................................
	freopen("input.txt", "r", stdin);
	int __size__ = 256 << 20; // 256MB
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	#endif //...........................................................................................................

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i].first);
		arr[i].second = i;
	}
	sort(arr, arr + n);
	ll ans = 0;

	g.build(1, 0, n - 1, n);
	matrix<ll> rm_have(3, 3), rm_havent(3, 3);
	for (int i = n - 1, link = n - 1; i >= 0; i--) {
		int rlink = link;
		while(link >= 0 && arr[link].first >= i + 1) link--;
		for (int j = rlink; j > link; j--) {
			g.upd(arr[j].second, 1);
		}
		ans = ans * (i - link) % mod;
		add(ans, (g.tree[1].sum - g.tree[1].already_set_after_sum.second + g.tree[1].minus_set_after_sum.second) % mod);
		rm_havent.danweiju();
		rm_have.danweiju();
		rm_havent[0][0] = rm_havent[0][1] = rm_havent[0][2] = 1;
		rm_have[0][0] = rm_have[0][1] = rm_have[0][2] = 1;
		for (int j = rlink; j > link; j--) {
			if (arr[j].second > 0) {
				g.upd(0, arr[j].second - 1, 1, rm_have, rm_havent);
			}
		}
		rm_havent.danweiju();
		rm_have.danweiju();
		rm_havent[0][0] = i - link; rm_havent[1][1] = i - link; rm_havent[2][2] = i - link - 1;
		rm_have[0][0] = i - link - 1; rm_have[1][1] = i - link - 1; rm_have[2][2] = i - link - 2;
		g.upd(0, n - 1, 1, rm_have, rm_havent);
	}

	cout << ans << endl;

    return 0;
}



Measured memory_bytes: 183168