#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

#include <cassert>
#include <utility>

namespace nachia{

// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
    long long x = 1, y = 0;
    while(b){
        long long u = a / b;
        std::swap(a-=b*u, b);
        std::swap(x-=y*u, y);
    }
    return std::make_pair(x, a);
}

} // namespace nachia

namespace nachia{

template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:

    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x){
        if(x < 0){
            if(0 <= x+MOD) return x + MOD;
            return MOD - ((-(x+MOD)-1) % MOD + 1);
        }
        return x % MOD;
    }

    StaticModint() : x(0){}
    StaticModint(const my_type& a) : x(a.x){}
    StaticModint& operator=(const my_type&) = default;
    template< class Elem >
    StaticModint(Elem v) : x(safe_mod(v)){}
    unsigned int operator*() const { return x; }
    my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; }
    my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; }
    bool operator==(const my_type& r) const { return x == r.x; }
    my_type pow(unsigned long long i) const {
        my_type a = *this, res = 1;
        while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
    unsigned int val() const { return x; }
    int hval() const { return int(x > MOD/2 ? x - MOD : x); }
    static constexpr unsigned int mod() { return MOD; }
    static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};

} // namespace nachia

namespace nachia{

template<unsigned int MOD>
struct PrimitiveRoot{
    using u64 = unsigned long long;
    static constexpr u64 powm(u64 a, u64 i) {
        u64 res = 1, aa = a;
        for( ; i; i /= 2){
            if(i & 1) res = res * aa % MOD;
            aa = aa * aa % MOD;
        }
        return res;
    }
    static constexpr bool ExamineVal(unsigned int g){
        u64 t = MOD - 1;
        for(u64 d=2; d*d<=t; d+=1+(d&1)) if(t % d == 0){
            if(powm(g, (MOD - 1) / d) == 1) return false;
            while(t % d == 0) t /= d;
        }
        if(t != 1) if(powm(g, (MOD - 1) / t) == 1) return false;
        return true;
    }
    static constexpr unsigned int GetVal(){
        for(u64 x=2; x<MOD; x++) if(ExamineVal(x)) return x;
        return 0;
    }
    static const unsigned int val = GetVal();
};

} // namespace nachia

namespace nachia {

template<class mint>
struct NttInterface{

template<class Iter>
void Butterfly(Iter, int) const {}

template<class Iter>
void IButterfly(Iter, int) const {}

template<class Iter>
void BitReversal(Iter a, int N) const {
    for(int i=0, j=0; j<N; j++){
        if(i < j) std::swap(a[i], a[j]);
        for(int k = N>>1; k > (i^=k); k>>=1);
    }
}

};

} // namespace nachia

namespace nachia{

int Popcount(unsigned long long c){
#ifdef __GNUC__
    return __builtin_popcountll(c);
#else
    c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
    c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
    c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
    c = (c * (~0ull/257)) >> 56;
    return c;
#endif
}

// please ensure x != 0
int MsbIndex(unsigned long long x){
    assert(x != 0ull);
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    using u64 = unsigned long long;
    int q = (x >> 32) ? 32 : 0;
    auto m = x >> q;
    constexpr u64 hi = 0x88888888;
    constexpr u64 mi = 0x11111111;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 31;
    q += (m & 0xf) << 2;
    q += 0x3333333322221100 >> (((x >> q) & 0xf) << 2) & 0xf;
    return q;
#endif
}

// please ensure x != 0
int LsbIndex(unsigned long long x){
    assert(x != 0ull);
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return MsbIndex(x & -x);
#endif
}

}

#include <iterator>
#include <array>

namespace nachia{

template <class mint>
struct NttFromAcl : NttInterface<mint> {

using u32 = unsigned int;
using u64 = unsigned long long;
    
static int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (u32)(n)) x++;
    return x;
}
    
static constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

struct fft_info {
    static constexpr u32 g = nachia::PrimitiveRoot<mint::mod()>::val;
    static constexpr int rank2 = bsf_constexpr(mint::mod()-1);
    using RootTable = std::array<mint, rank2+1>;
    RootTable root, iroot, rate3, irate3;

    fft_info(){
        root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
        iroot[rank2] = root[rank2].inv();
        for(int i=rank2-1; i>=0; i--){
            root[i] = root[i+1] * root[i+1];
            iroot[i] = iroot[i+1] * iroot[i+1];
        }
        mint prod = 1, iprod = 1;
        for(int i=0; i<=rank2-3; i++){
            rate3[i] = root[i+3] * prod;
            irate3[i] = iroot[i+3] * iprod;
            prod *= iroot[i+3];
            iprod *= root[i+3];
        }
    }
};

template<class RandomAccessIterator>
void Butterfly(RandomAccessIterator a, int n) const {
    int h = ceil_pow2(n);

    static const fft_info info;

    int len = 0;
    if((h-len)%2 == 1){
        int p = 1 << (h-len-1);
        for(int i=0; i<p; i++){
            mint l = a[i], r = a[i+p];
            a[i] = l+r; a[i+p] = l-r;
        }
        len++;
    }
    for( ; len < h; len += 2){
        int p = 1 << (h-len-2);
        mint rot = 1, imag = info.root[2];
        u64 mod2 = u64(mint::mod()) * mint::mod();
        for(int s=0; s<(1<<len); s++){
            if(s) rot *= info.rate3[LsbIndex(~(u32)(s-1))];
            mint rot2 = rot * rot;
            mint rot3 = rot2 * rot;
            int offset = (s << (h-len)) + p;
            for(int i=offset-p; i<offset; i++){
                u64 a0 = u64(a[i].val());
                u64 a1 = u64(a[i+p].val()) * rot.val();
                u64 a2 = u64(a[i+2*p].val()) * rot2.val();
                u64 a3 = u64(a[i+3*p].val()) * rot3.val();
                u64 a1na3imag = u64(mint(a1 + mod2 - a3).val()) * imag.val();
                u64 na2 = mod2 - a2;
                a[i] = a0 + a2 + a1 + a3;
                a[i+1*p] = a0 + a2 + (2 * mod2 - (a1 + a3));
                a[i+2*p] = a0 + na2 + a1na3imag;
                a[i+3*p] = a0 + na2 + (mod2 - a1na3imag);
            }
        }
    }
}

template<class RandomAccessIterator>
void IButterfly(RandomAccessIterator a, int n) const {
    int h = ceil_pow2(n);

    static const fft_info info;
    constexpr int MOD = mint::mod();

    int len = h;
    for( ; 1 < len; len -= 2){
        int p = 1 << (h-len);
        mint irot = 1, iimag = info.iroot[2];
        for(int s=0; s<(1<<(len-2)); s++){
            if(s) irot *= info.irate3[LsbIndex(~(u32)(s-1))];
            mint irot2 = irot * irot;
            mint irot3 = irot2 * irot;
            int offset = (s << (h-len+2)) + p;
            for(int i=offset-p; i<offset; i++){
                u64 a0 = a[i].val();
                u64 a1 = a[i+p].val();
                u64 a2 = a[i+2*p].val();
                u64 a3 = a[i+3*p].val();
                u64 a2na3iimag = mint((a2 + MOD - a3) * iimag.val()).val();
                a[i] = a0 + a1 + a2 + a3;
                a[i+p] = (a0 + (MOD - a1) + a2na3iimag) * irot.val();
                a[i+2*p] = (a0 + a1 + (MOD - a2) + (MOD - a3)) * irot2.val();
                a[i+3*p] = (a0 + (MOD - a1) + (MOD - a2na3iimag)) * irot3.val();
            }
        }
    }
    if(len == 1){
        int p = 1 << (h-len);
        for(int i=0; i<p; i++){
            mint l = a[i], r = a[i+p];
            a[i] = l+r; a[i+p] = l-r;
        }
    }
}

};

} // namespace nachia

namespace nachia {

struct BigintDecMulManager {
    using Int = int;
    using Arr = std::vector<Int>;
    using u32 = unsigned int;
    using i64 = long long;
    static const Int B = 1000000000;
    static const u32 MOD0 = 0x1c000001;
    static const u32 MOD1 = 0x6c000001;
    static const u32 MOD2 = 0x78000001;
    static const u32 I0_M1 = 1540148431;
    static const u32 I01_M2 = 1050399624;
    static const u32 I1_M2 = 10;
    static const u32 IB_M1 = 1575545083;
    static const u32 IB_M2 = 65929464;

    template<u32 MOD>
    static std::vector<u32> convMod(int z, int n, const Arr& a, const Arr& b){
        using Mint = StaticModint<MOD>;
        static auto ntt = NttFromAcl<Mint>();
        std::vector<Mint> a2(z);
        for(int i=0; i<(int)a.size(); i++) a2[i] = a[i];
        std::vector<Mint> b2(z);
        for(int i=0; i<(int)b.size(); i++) b2[i] = b[i];
        Mint c = Mint(z).inv();
        ntt.Butterfly(a2.begin(), z);
        ntt.Butterfly(b2.begin(), z);
        for(int i=0; i<z; i++) a2[i] *= b2[i] * c;
        ntt.IButterfly(a2.begin(), z);
        std::vector<u32> res(n);
        for(int i=0; i<n; i++) res[i] = a2[i].val();
        return res;
    }
    template<u32 M>
    static inline StaticModint<M> SubMod(u32 a, u32 b){
        return StaticModint<M>::raw(a<b ? a+M-b : a-b);
    }

    static Arr BigintDecMul(const Arr& a, const Arr& b){
        int n = a.size() + b.size();
        int n2 = 1; while(n2 < n) n2 *= 2;
        auto c0 = convMod<MOD0>(n2, n-1, a, b);
        auto c1 = convMod<MOD1>(n2, n-1, a, b);
        auto c2 = convMod<MOD2>(n2, n-1, a, b);
        std::vector<i64> c(n+1);
        using MintB = StaticModint<B>;
        using Mint1 = StaticModint<MOD1>;
        using Mint2 = StaticModint<MOD2>;
        auto i0m1 = Mint1::raw(I0_M1);
        auto i01m2 = Mint2::raw(I01_M2);
        auto ibm1 = Mint1::raw(IB_M1);
        auto ibm2 = Mint2::raw(IB_M2);
        auto i1m2 = Mint2::raw(I1_M2);
        auto m01_b = MintB::raw(MOD0) * MintB(MOD1);
        for(int i=0; i<n-1; i++){
            u32 d0to1 = (i0m1 * SubMod<MOD1>(c1[i], c0[i])).val();
            Mint2 x01m2 = Mint2::raw(c0[i]) + Mint2::raw(MOD0) * Mint2::raw(d0to1);
            MintB x01mB = MintB::raw(c0[i]) + MintB::raw(MOD0) * MintB(d0to1);
            MintB xmB = x01mB + m01_b * MintB((i01m2 * SubMod<MOD2>(c2[i], x01m2.val())).val());
            c[i] += xmB.val();
            Mint1 y1 = SubMod<MOD1>(c1[i], xmB.val()) * ibm1;
            Mint2 y2 = SubMod<MOD2>(c2[i], xmB.val()) * ibm2;
            i64 y12 = (i64)y1.val() + (i64)MOD1 * (i64)(i1m2 * SubMod<MOD2>(y2.val(), y1.val())).val();
            c[i+1] += y12 % B; c[i+2] += y12 / B;
        }
        Arr res(n);
        for(int i=0; i<n; i++){
            res[i] = c[i]%B;
            c[i+1] += c[i]/B;
        }
        if(res.back() == 0) res.pop_back();
        return res;
    }

};

};


namespace nachia {

struct BigintDec{
    using Int = int;
    using Arr = std::vector<Int>;

    BigintDec() : sign(0), A(0) {}
    BigintDec(int z){
        if(z == 0){ sign = 0; }
        else if(z < 0){ sign = -1; A = Arr(1, -z); }
        else{ sign = 1; A = Arr(1, z); }
    }
    BigintDec(const std::string& s) : sign(1) {
        auto it = s.begin();
        if(it != s.end()){
            if(*it == '-'){ sign = -1; it++; }
            else if(*it == '+'){ it++; }
        }
        while(it != s.end() && *it == '0') it++;
        if(it == s.end()){ sign = 0; }
        else {
            auto f = (s.end() - it);
            int e = int((f-1) / 9);
            int d = int((f-1) % 9);
            A.assign(e + 1, 0);
            for( ; it!=s.end(); it++){
                assert('0' <= *it && *it <= '9');
                A[e] = A[e] * 10 + (*it - '0');
                d--; if(d < 0){ d = 8; e -= 1; }
            }
        }
    }

    BigintDec operator+(const BigintDec& r) const {
        if(r.isZero()) return *this;
        if(isZero()) return r;
        auto x = (sign == r.sign) ?
            uintSum(*this, r) : uintDiff(*this, r);
        x.sign *= sign;
        return x;
    }

    BigintDec operator-() const { return raw(-sign, A); }

    BigintDec operator-(const BigintDec& r) const {
        if(r.isZero()) return *this;
        if(isZero()) return -r;
        auto x = (sign == r.sign) ?
            uintDiff(*this, r) : uintSum(*this, r);
        x.sign *= sign;
        return x;
    }

    BigintDec operator*(const BigintDec& r) const {
        if(isZero() || r.isZero()) return Zero();
        return raw(sign * r.sign, uintMul(*this, r));
    }

    std::pair<BigintDec, BigintDec> divrem(const BigintDec& r) const {
        assert(!r.isZero());
        if(isZero() || CmpAbs(*this, r) == 1) return { Zero(), *this };
        auto invr = r.invFlex(len()+1);
        auto a2 = (*this * invr).shiftRight(len() + r.len() + 2);
        a2.sign = sign * r.sign;
        auto rem = (*this) - (r * a2);
        if(CmpAbs(r, rem) >= 0){
            rem = rem - r;
            a2 = a2 + BigintDec("1");
        }
        return std::make_pair(std::move(a2), std::move(rem));
    }

    BigintDec operator/(const BigintDec& r){
        assert(!r.isZero());
        return divrem(r).first;
    }

    BigintDec& operator*=(int x){
        if(x == 0) return (*this) = Zero();
        i64 y = std::abs(x);
        i64 c = 0;
        for(int i=0; i<len(); i++){
            c += A[i] * y;
            A[i] = c % B; c /= B;
        }
        if(c >= B){ A.push_back(c % B); c /= B; }
        if(c) A.push_back(c);
        if(x < 0) sign = -sign;
        return *this;
    }

    static BigintDec Zero(){ return BigintDec(); }
    bool isZero() const { return sign == 0; }
    std::string toString() const {
        if(isZero()) return "0";
        std::string s;
        for(int i=0; i<len()-1; i++){
            int a = A[i];
            for(int d=0; d<9; d++){ s.push_back('0'+a%10); a /= 10; }
        }
        for(Int a=A[len()-1]; a!=0; a/=10) s.push_back('0'+a%10);
        if(sign < 0) s.push_back('-');
        std::reverse(s.begin(), s.end());
        return s;
    }
    bool operator<(const BigintDec& r) const {
        if(sign != r.sign) return sign < r.sign;
        return CmpAbs(*this, r) == sign;
    }
    bool operator>(const BigintDec& r) const { return r < *this; }
    bool operator<=(const BigintDec& r) const { return !(r < *this); }
    bool operator>=(const BigintDec& r) const { return !(*this < r); }
    bool operator==(const BigintDec& r) const { return sign == r.sign && A == r.A; }
    bool operator!=(const BigintDec& r) const { return !(*this == r); }
private:
    using Self = BigintDec;
    using i64 = long long;
    int sign;
    std::vector<Int> A;
    static const int B = 1000000000;
    int len() const { return int(A.size()); }
    Int dig(int z) const { return z < len() ? A[z] : 0; }
    Int& operator[](int z){ return A[z]; }
    const Int& operator[](int z) const { return A[z]; }
    static int CmpUintPos(const Self& l, const Self& r){
        if(l.len() != r.len()) return std::max(l.len(), r.len()) - 1;
        for(int i=l.len()-1; i>=0; i--) if(l[i] != r[i]) return i;
        return -1;
    }
    static int CmpAbs(const Self& l, const Self& r){
        int k = CmpUintPos(l, r);
        if(k < 0) return 0;
        return l.dig(k) < r.dig(k) ? 1 : -1;
    }
    static Self raw(int sign, Arr a){
        if(a.empty()) sign = 0;
        while(!a.empty() && a.back() == 0) a.pop_back();
        Self res; res.sign = sign; res.A = std::move(a);
        return res;
    }
    static Self uintDiff2(const Self& l, const Self& r, int k){
        Arr A(k + 1);
        for(int i=0; i<=k; i++) A[i] = l[i];
        int j = std::min(k+1, r.len());
        Int v = 0;
        for(int i=0; i<j; i++){
            v = v + A[i] - r[i];
            if(v < 0){ A[i] = v + B; v = -1; }
            else { A[i] = v; v = 0; }
        }
        for(int i=j; v!=0; i++){
            v = v + A[i];
            if(v < 0){ A[i] = v + B; v = -1; }
            else { A[i] = v; v = 0; }
        }
        return raw(1, std::move(A));
    }
    static Self uintDiff(const Self& l, const Self& r){
        int k = CmpUintPos(l, r);
        if(k == -1) return Zero();
        if(l.dig(k) > r.dig(k)) return uintDiff2(l, r, k);
        auto x = uintDiff2(r, l, k); x.sign = -x.sign;
        return x;
    }
    static Self uintSum(const Self& l, const Self& r){
        if(l.len() > r.len()) return uintSum(r, l);
        Arr A(r.len() + 1);
        for(int i=0; i<l.len(); i++) A[i] = l[i];
        Int v = 0;
        for(int i=0; i<r.len(); i++){
            v = v + A[i] + r[i];
            if(B <= v){ A[i] = v - B; v = 1; }
            else { A[i] = v; v = 0; }
        }
        if(v != 0) A[r.len()] = v; else A.pop_back();
        return raw(1, std::move(A));
    }
    static Arr uintMul(const Self& l, const Self& r){
        if(l.len() >= 30 && r.len() >= 30){
            return BigintDecMulManager::BigintDecMul(l.A, r.A);
        }
        int z = l.len() + r.len();
        Arr a(z);
        for(int i=0; i<l.len(); i++) for(int j=0; j<r.len(); j++){
            i64 x = (i64)(l[i]) * r[j] + a[i+j];
            a[i+j] = x % B; a[i+j+1] += x / B;
        }
        if(a.back() == 0) a.pop_back();
        return a;
    }
    Self shiftLeft(int delta) const {
        if(isZero()) return Zero();
        Arr a(len() + delta);
        for(int i=0; i<len(); i++) a[i+delta] = A[i];
        return raw(sign, std::move(a));
    }
    Self shiftRight(int delta) const {
        if(len() <= delta) return Zero();
        Arr a(len() - delta);
        for(int i=delta; i<len(); i++) a[i-delta] = A[i];
        return raw(sign, std::move(a));
    }
    Self shiftToLength(int tg) const {
        return len() < tg ? shiftLeft(tg - len())
            : shiftRight(len() - tg);
    }
    void negate(){ sign = -sign; }
    Self invFlex(int prec) const {
        Int t = B / (A[len()-1] + 1);
        auto a2 = *this; a2 *= t;
        auto b2 = a2.invPrec(prec);
        b2 *= t;
        return b2;
    }
    Self invPrec(int prec){
        if(prec == 1){
            Int b = A[len()-1];
            Arr a(3); a[2] = 1; a[1] = i64(B) * B / b - B;
            return raw(sign, std::move(a));
        }
        int subp = (prec + 1) / 2;
        auto b = invPrec(subp);
        auto ab = (shiftToLength(prec+1) * b).shiftRight(subp+1);
        auto ab2 = Self("2").shiftLeft(prec+1) - ab;
        return (ab2 * b).shiftRight(subp + 1);
    }
};

}

namespace {

std::istream& operator>>(std::istream& i, nachia::BigintDec& d){
    std::string s; i >> s;
    d = nachia::BigintDec(s);
    return i;
}

std::ostream& operator<<(std::ostream& o, const nachia::BigintDec& d){
    return o << d.toString();
}

}


namespace nachia {

template <class T> struct FenwickTree {
public:
    FenwickTree() : _n(0){}
    explicit FenwickTree(int n, T ZERO = T(0)) : _n(n), a(n, ZERO){}
    void add(int p, T x){
        assert(0 <= p && p < _n);
        p++;
        while(p <= _n){
            a[p-1] += T(x);
            p += p & -p;
        }
    }
    T sum(int r){
        return sumr(r);
    }
    T sum(int l, int r){
        return sumr(r) - sumr(l);
    }
private:
    int _n;
    std::vector<T> a;

    T sumr(int r){
        T s = 0;
        while(r > 0){
            s += a[r-1];
            r -= r & -r;
        }
        return s;
    }
};

}  // namespace nachia

namespace nachia {
    template<class T> using PointAddRangeSumFwt = FenwickTree<T>;
} // namespace nachia

using Int = nachia::BigintDec;

void testcase(){
  ll N; cin >> N;
  V<ll> P(N); REP(i,N){ cin >> P[i]; P[i]--; }
  nachia::PointAddRangeSumFwt<ll> ds(N);
  V<ll> A(N);
  REP(i,N){
    A[i] = P[i] - ds.sum(0, P[i]);
    ds.add(P[i], 1);
  }
  auto dfs = [&](auto& dfs, ll l, ll r) -> pair<Int, Int> {
    if(l + 1 == r) return { Int(A[l]), Int(N-l) };
    ll m = (l + r) / 2;
    auto [al, bl] = dfs(dfs, l, m);
    auto [ar, br] = dfs(dfs, m, r);
    return { al * br + ar, bl * br };
  };
  cout << (dfs(dfs, 0, N).first + 1).toString() << "\n";
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  testcase();
  return 0;
}