#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
struct BIT {
int n;
vector<ll> B1, B2;
BIT(int n) : n(n), B1(n + 1, 0), B2(n + 1, 0) {}
void update(vector<ll>& B, int i, ll v) {
for (; i <= n; i += i & -i) B[i] += v;
}
void range_update(int l, int r, ll v) {
// add v to range [l, r]
update(B1, l, v);
update(B1, r + 1, -v);
update(B2, l, v * (l - 1));
update(B2, r + 1, -v * r);
}
ll query(const vector<ll>& B, int i) {
ll res = 0;
for (; i > 0; i -= i & -i) res += B[i];
return res;
}
ll prefix_sum(int i) {
return query(B1, i) * i - query(B2, i);
}
ll range_sum(int l, int r) {
return prefix_sum(r) - prefix_sum(l - 1);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << fixed << setprecision(0);
ll n, curr = 1, ans = 0; cin >> n;
vector<ll> a(n); for (auto &x: a) cin >> x;
vector<ll> ac(n); for (ll i = 0; i < n; i++) ac[i] = a[i];
sort(ac.begin(), ac.end());
map<ll, ll> m; for (auto x: ac) if (!m.count(x)) m[x] = curr++;
for (ll i = 0; i < n; i++) a[i] = m[a[i]];
vector<ll> f(n + 1); f[0] = 1; for (ll i = 1; i <= n; i++) f[i] = (i * f[i - 1]) % MOD;
BIT bit(n + 1); for (ll i = 1; i <= n; i++) bit.range_update(i, i, 1);
for (ll i = 0; i < n; i++)
ans = (ans + bit.range_sum(1, a[i] - 1) * f[n - 1 - i]) % MOD,
bit.range_update(a[i], a[i], -1);
cout << ans + 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |