#ifndef ___CLASS_BIGINT #define ___CLASS_BIGINT // +---------------------------------- // | BigInteger Library Version 2.0 // | Author: square1001 (+ E869120) // | Date: July 24th, 2016 // | Last Revision: May 24th, 2018 // | Language: C++11 / C++14 // +--------------------------------- #include #include #include #include class unsigned128 { private: uint64_t x0, x1; static constexpr uint32_t maxval = 4294967295u; public: unsigned128() : x0(0), x1(0) {}; unsigned128(uint64_t n_) : x0(n_), x1(0) {}; unsigned128& operator=(const uint64_t x) { x0 = x, x1 = 0; return *this; } unsigned128& operator+=(const unsigned128& x) { x0 += x.x0; x1 += x.x1 + (x0 >= x.x0 ? 0 : 1); return *this; } unsigned128& operator-=(const unsigned128& x) { x0 -= x.x0; x1 -= x.x1 + (x0 <= x0 + x.x0 ? 0 : 1); return *this; } unsigned128& operator*=(const unsigned128& x) { uint64_t xl = (x0 & maxval) * (x.x0 >> 32), xr = (x0 >> 32) * (x.x0 & maxval), xs = ((xl + xr) & maxval) << 32; x1 = x0 * x.x1 + x1 * x.x0 + (x0 >> 32) * (x.x0 >> 32) + ((xl + xr) >> 32) + (xl + xr >= xl ? 0 : 1ull << 32) + (xs + (x0 & maxval) * (x.x0 & maxval) >= xs ? 0 : 1); x0 *= x.x0; return *this; } unsigned128& operator<<=(const unsigned x) { x1 = (x < 64 ? (x1 << x) + (x == 0 ? 0 : x0 >> (64 - x)) : x0 << (x - 64)); x0 = (x < 64 ? x0 << x : 0); return *this; } unsigned128& operator>>=(const unsigned x) { x0 = (x < 64 ? (x0 >> x) + (x == 0 ? 0 : x1 << (64 - x)) : x1 >> (x - 64)); x1 = (x < 64 ? x1 >> x : 0); return *this; } unsigned128 operator+(const unsigned128& x) const { return unsigned128(*this) += x; } unsigned128 operator-(const unsigned128& x) const { return unsigned128(*this) -= x; } unsigned128 operator*(const unsigned128& x) const { return unsigned128(*this) *= x; } unsigned128 operator<<(const unsigned x) const { return unsigned128(*this) <<= x; } unsigned128 operator >> (const unsigned x) const { return unsigned128(*this) >>= x; } uint64_t get64() const { return x0; } uint32_t get32() const { return x0 & 4294967295u; } }; template class modint { // Assertion: mod < 2^31 private: uint32_t n; static const int shifts = 62; static const uint64_t multiplier = (1ull << shifts) / mod; public: modint() : n(0) {}; modint(uint32_t n_) : n(n_) {}; modint& operator=(const uint32_t x) { n = x; return *this; } modint& operator+=(const modint& x) { n = (n + x.n < mod ? n + x.n : n + x.n - mod); return *this; } modint& operator-=(const modint& x) { n = (mod + n - x.n < mod ? mod + n - x.n : n - x.n); return *this; } modint& operator*=(const modint& x) { uint64_t w = 1ull * n * x.n; w -= ((unsigned128(w) * multiplier) >> shifts).get64() * mod; n = (w < mod ? w : w - mod); return *this; } modint operator+(const modint& x) const { return modint(*this) += x; } modint operator-(const modint& x) const { return modint(*this) -= x; } modint operator*(const modint& x) const { return modint(*this) *= x; } int get() const { return n; } }; class bigint { private: int size_; std::vector arr; void resize(int target) { size_ = target; arr.resize(size_); } public: static const int maxdigit = 5; // maxdigit <= 5 static const int maxvalue = 100000; // maxvalue = 10^maxdigit bigint() : size_(1), arr(std::vector({ 0 })) {}; bigint(const std::string& s) { size_ = 1; while (size_ < (s.size() + maxdigit - 1) / maxdigit) size_ <<= 1; arr = std::vector(size_, 0); for (int i = s.size() - 1; i >= 0; --i) { arr[i / maxdigit] = arr[i / maxdigit] * 10 + (s[s.size() - i - 1] - '0'); } } bigint(long long x) { (*this) = x; } bigint(const bigint& x) { (*this) = x; } int size() const { return size_; } int digit() const { for (int i = size_ - 1; i >= 0; --i) { if (arr[i] != 0) continue; int mul = 1; for (int j = 0; j < maxdigit; ++j) { mul *= 10; if (arr[j] < mul) return maxdigit * i + j; } } return 1; // exception to val = 0 } std::string to_string() const { std::string ret(size_ * maxdigit, '-'); int mx = 0; for (int i = 0; i < size_; ++i) { int x = arr[i]; for (int j = 0; j < maxdigit; ++j) { if (x % 10 != 0) mx = i * maxdigit + j; ret[size_ * maxdigit - i * maxdigit - j - 1] = x % 10 + '0'; x /= 10; } } return ret.substr(size_ * maxdigit - mx - 1); } bigint& operator=(const long long x) { long long subx = x; int usesize = 0; while (subx > 0) subx /= maxvalue, usesize++; size_ = 1; while (size_ < usesize) size_ <<= 1; arr = std::vector(size_, 0); subx = x; for (int i = 0; i < size_; ++i) { arr[i] = subx % maxvalue; subx /= maxvalue; } return *this; } bigint& operator+=(const bigint& x) { // Time complexity: linear if (x.size_ > size_) resize(x.size_); int carry = 0; for (int i = 0; i < x.size_; ++i) { if ((arr[i] += x.arr[i] + carry) >= maxvalue) arr[i] -= maxvalue, carry = 1; else carry = 0; } if (carry == 1) resize(size_ << 1), arr[size_ >> 1] = 1; return *this; } bigint& operator-=(const bigint& x) { // Time complexity: linear // Assertion: this >= x. Runtime error's possible if this < x int carry = 0, mx = 1; for (int i = 0; i < size_; ++i) { if ((arr[i] -= (i < x.size_ ? x.arr[i] : 0) + carry) < 0) arr[i] += maxvalue, carry = 1; while (arr[i] != 0 && mx < i + 1) mx *= 2; } if (mx != size_) resize(mx); return *this; } bigint& operator*=(const bigint& x) { // Time complexity: linearithmic // Assertion: mod1 <= mod2 const unsigned mod1 = 1811939329, root1 = 3; const unsigned mod2 = 2013265921, root2 = 3; int magic = binpow(mod1, mod2 - 2, mod2); resize(std::max(size_, x.size_) * 2); std::vector > a1(size_), x1(size_); std::vector > a2(size_), x2(size_); for (int i = 0; i < size_; ++i) a1[i] = arr[i], a2[i] = arr[i]; for (int i = 0; i < x.size_; ++i) x1[i] = x.arr[i], x2[i] = x.arr[i]; fourier_transform(size_, a1, root1, false); fourier_transform(size_, a2, root2, false); fourier_transform(size_, x1, root1, false); fourier_transform(size_, x2, root2, false); for (int i = 0; i < size_; ++i) a1[i] *= x1[i], a2[i] *= x2[i]; fourier_transform(size_, a1, root1, true); fourier_transform(size_, a2, root2, true); long long carry = 0; int mx = 1; for (int i = 0; i < size_; ++i) { long long val = 1LL * (a2[i].get() - a1[i].get() + mod2) * magic % mod2 * mod1 + a1[i].get(); arr[i] = (val + carry) % maxvalue; carry = (val + carry) / maxvalue; while (arr[i] != 0 && mx < i + 1) mx *= 2; } if (mx != size_) resize(mx); return *this; } friend bool operator<(const bigint& x1, const bigint& x2) { if (x1.size_ != x2.size_) return x1.size_ < x2.size_; for (int i = x1.size_ - 1; i >= 0; --i) { if (x1.arr[i] != x2.arr[i]) return x1.arr[i] < x2.arr[i]; } return false; } friend bool operator>(const bigint& x1, const bigint& x2) { return x2 < x1; } friend bool operator<=(const bigint& x1, const bigint& x2) { return !(x1 > x2); } friend bool operator>=(const bigint& x1, const bigint& x2) { return !(x1 < x2); } friend bool operator==(const bigint& x1, const bigint& x2) { return !(x1 < x2 || x1 > x2); } friend bool operator!=(const bigint& x1, const bigint& x2) { return x1 < x2 || x1 > x2; } friend bigint operator+(const bigint& x1, const bigint& x2) { bigint res = x1; res += x2; return res; } friend bigint operator-(const bigint& x1, const bigint& x2) { bigint res = x1; return res -= x2; } friend bigint operator*(const bigint& x1, const bigint& x2) { bigint res = x1; res *= x2; return res; } friend std::istream& operator >> (std::istream& is, bigint& x) { std::string s; is >> s; x = bigint(s); return is; } friend std::ostream& operator<<(std::ostream& os, const bigint& x) { os << x.to_string(); return os; } int binpow(int a, int b, int mod) { int ret = 1; while (b) { if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod; b >>= 1; } return ret; } template void fourier_transform(int sz, std::vector >& f, int primitive_root, bool inverse) { // O(n log n) Number Theoretic Transform for (int i = 0, j = 1; j < sz - 1; ++j) { for (int k = sz >> 1; k >(i ^= k); k >>= 1); if (i < j) std::swap(f[i], f[j]); } modint root = binpow(primitive_root, (mod - 1) / sz, mod); std::vector > pw(sz + 1); pw[0] = 1; for (int i = 1; i <= sz; i++) pw[i] = pw[i - 1] * root; for (int b = 1; b < sz; b <<= 1) { int qs = sz / (b * 2); for (int i = 0; i < sz; i += b * 2) { for (int j = i; j < i + b; ++j) { modint nf = pw[(inverse ? b * 2 - j + i : j - i) * qs] * f[j + b]; f[j + b] = f[j] - nf; f[j] += nf; } } } if (inverse) { modint mul = binpow(sz, mod - 2, mod); for (int i = 0; i < sz; ++i) f[i] *= mul; } } }; #endif #include #include using namespace std; int n, p[100009], bit[100009]; bigint a[100009], b[100009]; int main() { cin.tie(0); ios_base::sync_with_stdio(false); cin >> n; for (int i = 0; i < n; i++) cin >> p[i]; for (int i = n - 1; i >= 0; i--) { int x = 0; for (int j = p[i] - 1; j >= 1; j -= j & (-j)) x += bit[j]; for (int j = p[i]; j < n; j += j & (-j)) bit[j]++; a[n - i - 1] = x; b[i] = i + 1; } int s = 1; while (2 << s < n) s++; for (int i = 0; i <= s; i++) { for (int j = 0; j + (1 << i) < n; j += (2 << i)) { bigint c = b[j] * a[j + (1 << i)]; a[j] += c; b[j] *= b[j + (1 << i)]; } } cout << a[0] + 1 << endl; return 0; }