結果
| 問題 | No.1300 Sum of Inversions |
| ユーザー |
 naskya
|
| 提出日時 | 2020-11-27 23:10:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 517 ms / 2,000 ms |
| コード長 | 26,932 bytes |
| コンパイル時間 | 2,810 ms |
| コンパイル使用メモリ | 222,504 KB |
| 最終ジャッジ日時 | 2025-01-16 08:23:19 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 |
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:637:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
637 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
ソースコード
#pragma region template// clang-format off#include <bits/stdc++.h>#if (defined LOCAL_JUDGE) || (!__has_include (<cp/debugger.hpp>))#define see(...) ((void) 0)#define here(...) ((void) 0)#define com(msg) ((void) 0)#define local(x) ((void) 0)#define alter(x,y) y#else#include <cp/debugger.hpp>#define see(...) debugger::print(#__VA_ARGS__, __VA_ARGS__)#define here(...) debugger::output << "[Debug] " << #__VA_ARGS__ << (strlen(#__VA_ARGS__) ? " | " : "") << "line " << __LINE__ << " (" << __func__ <<")\n"#define com(msg) debugger::output << "[Debug] " << msg << "\n"#define local(x) do{x} while(0)#define alter(x,y) x#endif#ifdef NDEBUG#define NOEXCEPT noexcept#define M_assert(expr) ((void) 0)#define O_assert(expr) ((void) 0)#elif defined ONLINE_JUDGE#define NOEXCEPT noexcept#define M_assert(expr) do{if(__builtin_expect(!(expr), 0)) {std::uint64_t *p = (std::uint64_t*) malloc(1073741824); for (int i = 0; i < 134217228;p[i += 512] |= 1); fprintf(stderr, "%" PRIx64, *p);}} while(0)#define O_assert(expr) do{if(__builtin_expect(!(expr), 0)) while(1) printf("Hello, world!\n");} while(0)#else#define NOEXCEPT#define M_assert(expr) assert(expr)#define O_assert(expr) assert(expr)#endif#define rep(i,n) for(int i = 0; i < (int)(n); i++)using std::string;using std::vector;[[maybe_unused]] constexpr int INF = 1000000005;[[maybe_unused]] constexpr long long LINF = 1000000000000000005LL;[[maybe_unused]] constexpr double EPS = 1e-9;[[maybe_unused]] constexpr int dy[8] = {1, 0, -1, 0, 1, 1, -1, -1};[[maybe_unused]] constexpr int dx[8] = {0, 1, 0, -1, -1, 1, 1, -1};template <class T> T Abs(T a) { return std::abs(a); }template <class S, class T, class ReturnType = std::common_type_t<S, T>> ReturnType Abs(S a, T b) { return std::abs((ReturnType) a - b); }template <class S, class T, class... Ts, class ReturnType = std::common_type_t<S, T, Ts...>> ReturnType Min(S a, T b, Ts... c) { if constexpr (sizeof...(Ts) > 0) return std::min((ReturnType) a, (ReturnType) Min(b, c...)); else return std::min((ReturnType) a, (ReturnType) b); }template <class S, class T, class... Ts, class ReturnType = std::common_type_t<S, T, Ts...>> ReturnType Max(S a, T b, Ts... c) { if constexpr (sizeof...(Ts) > 0) return std::max((ReturnType) a, (ReturnType) Max(b, c...)); else return std::max((ReturnType) a, (ReturnType) b); }// clang-format on#pragma endregionconstexpr int MOD = 998244353;#pragma region lib_mint#ifndef lib_mint#define lib_mint 1namespace lib {template <int modulo> class modint {int value;template <class T> constexpr int calc_inverse(T n) const noexcept {T b = modulo, u = 1, v = 0, t = 0;while (b > 0) {t = n / b;std::swap(n -= t * b, b);std::swap(u -= t * v, v);}return static_cast<int>(u);}template <class T> constexpr int clamp_ll(T v) const noexcept {if (modulo <= v || v < -modulo) v %= modulo;if (v < 0) v += modulo;return static_cast<int>(v);}constexpr void clamp_self(void) noexcept {if (0 <= value) {if (value < modulo) return;if (value < modulo * 2)value -= modulo;elsevalue -= modulo * 2;} else {if (-modulo < value)value += modulo;else if (-modulo * 2 < value)value += modulo * 2;else {value += modulo;value += modulo * 2;}}}public:/* constructor */constexpr modint(void) noexcept :value(0) {}template <class Valuetype> constexpr modint(const Valuetype v) noexcept {if constexpr (std::is_same_v<Valuetype, int>) {value = v;clamp_self();} else {value = clamp_ll(v);}}constexpr modint(const int v, [[maybe_unused]] const bool passthrough) noexcept :value(v) {}/* operator */constexpr modint<modulo> operator+(const modint<modulo> rhs) const noexcept {return modint<modulo>(value + rhs.value);}constexpr modint<modulo> operator-(const modint<modulo> rhs) const noexcept {return modint<modulo>(value - rhs.value);}constexpr modint<modulo> operator*(const modint<modulo> rhs) const noexcept {return modint<modulo>(static_cast<long long>(value) * rhs.value);}constexpr modint<modulo> operator/(const modint<modulo> rhs) const NOEXCEPT {O_assert(rhs.value != 0);return modint<modulo>(static_cast<long long>(value) * calc_inverse(rhs.value));}constexpr modint<modulo> operator%(const modint<modulo> rhs) const NOEXCEPT {com("[Warning] mint::operator% : Are you sure you want to do this?");O_assert(rhs.value != 0);return modint<modulo>(value % rhs.value, true);}constexpr modint<modulo> operator&(const modint<modulo> rhs) const noexcept {com("[Warning] mint::operator& : Are you sure you want to do this?");return modint<modulo>(value & rhs.value, true);}constexpr modint<modulo> operator|(const modint<modulo> rhs) const noexcept {com("[Warning] mint::operator| : Are you sure you want to do this?");return modint<modulo>(value | rhs.value);}constexpr modint<modulo> operator^(const modint<modulo> rhs) const noexcept {com("[Warning] mint::operator^ : Are you sure you want to do this?");return modint<modulo>(value ^ rhs.value);}constexpr modint<modulo> operator<<(const modint<modulo> rhs) const noexcept {com("[Warning] mint::operator<< : Are you sure you want to do this?");return modint<modulo>(static_cast<long long>(value) << rhs.value);}constexpr modint<modulo> operator>>(const modint<modulo> rhs) const noexcept {com("[Warning] mint::operator>> : Are you sure you want to do this?");return modint<modulo>(value >> rhs.value, true);}constexpr modint<modulo>& operator+=(const modint<modulo> rhs) noexcept {value += rhs.value;if (value >= modulo) value -= modulo;return *this;}constexpr modint<modulo>& operator-=(const modint<modulo> rhs) noexcept {value -= rhs.value;if (value < 0) value += modulo;return *this;}constexpr modint<modulo>& operator*=(const modint<modulo> rhs) noexcept {value = clamp_ll(static_cast<long long>(value) * rhs.value);return *this;}constexpr modint<modulo>& operator/=(const modint<modulo> rhs) NOEXCEPT {O_assert(rhs != 0);value = clamp_ll(static_cast<long long>(value) * calc_inverse(rhs.value));return *this;}constexpr modint<modulo>& operator%=(const modint<modulo> rhs) NOEXCEPT {com("[Warning] mint::operator%= : Are you sure you want to do this?");O_assert(rhs != 0);value %= rhs.value;if (value < 0) value += modulo;return *this;}constexpr modint<modulo>& operator&=(const modint<modulo> rhs) noexcept {com("[Warning] mint::operator&= : Are you sure you want to do this?");value &= rhs.value;return *this;}constexpr modint<modulo>& operator|=(const modint<modulo> rhs) noexcept {com("[Warning] mint::operator|= : Are you sure you want to do this?");value |= rhs.value;clamp_self();return *this;}constexpr modint<modulo>& operator^=(const modint<modulo> rhs) noexcept {com("[Warning] mint::operator^= : Are you sure you want to do this?");value ^= rhs.value;clamp_self();return *this;}constexpr modint<modulo>& operator<<=(const modint<modulo> rhs) noexcept {com("[Warning] mint::operator<<= : Are you sure you want to do this?");value = clamp_ll(static_cast<long long>(value) << rhs.value);return *this;}constexpr modint<modulo>& operator>>=(const modint<modulo> rhs) noexcept {com("[Warning] mint::operator>>= : Are you sure you want to do this?");value >>= rhs.value;return *this;}template <class RHStype> constexpr modint<modulo> operator+(const RHStype rhs) const noexcept {return modint<modulo>(static_cast<long long>(value) + rhs);}template <class RHStype> constexpr modint<modulo> operator-(const RHStype rhs) const noexcept {return modint<modulo>(static_cast<long long>(value) - rhs);}template <class RHStype> constexpr modint<modulo> operator*(const RHStype rhs) const noexcept {return modint<modulo>(static_cast<long long>(value) * rhs);}template <class RHStype> constexpr modint<modulo> operator/(const RHStype rhs) const NOEXCEPT {O_assert(rhs != 0);long long mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);return modint<modulo>(mul * value);}template <class RHStype> constexpr modint<modulo> operator%(const RHStype rhs) const NOEXCEPT {com("[Warning] mint::operator% : Are you sure you want to do this?");O_assert(rhs != 0);return modint<modulo>(value % rhs, true);}template <class RHStype> constexpr modint<modulo> operator&(const RHStype rhs) const noexcept {com("[Warning] mint::operator& : Are you sure you want to do this?");return modint<modulo>(value & rhs, true);}template <class RHStype> constexpr modint<modulo> operator|(const RHStype rhs) const noexcept {com("[Warning] mint::operator| : Are you sure you want to do this?");return modint<modulo>(value | rhs);}template <class RHStype> constexpr modint<modulo> operator^(const RHStype rhs) const noexcept {com("[Warning] mint::operator^ : Are you sure you want to do this?");return modint<modulo>(value ^ rhs);}template <class RHStype> constexpr modint<modulo> operator<<(const RHStype rhs) const noexcept {com("[Warning] mint::operator<< : Are you sure you want to do this?");return modint<modulo>(static_cast<long long>(value) << rhs);}template <class RHStype> constexpr modint<modulo> operator>>(const RHStype rhs) const noexcept {com("[Warning] mint::operator>> : Are you sure you want to do this?");return modint<modulo>(value >> rhs, true);}template <class RHStype> constexpr modint<modulo>& operator+=(const RHStype rhs) noexcept {value = clamp_ll(static_cast<long long>(value) + rhs);return *this;}template <class RHStype> constexpr modint<modulo>& operator-=(const RHStype rhs) noexcept {value = clamp_ll(static_cast<long long>(value) - rhs);return *this;}template <class RHStype> constexpr modint<modulo>& operator*=(const RHStype rhs) noexcept {value = clamp_ll(static_cast<long long>(value) * rhs);return *this;}template <class RHStype> constexpr modint<modulo>& operator/=(const RHStype rhs) NOEXCEPT {O_assert(rhs != 0);long long mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);value = clamp_ll(mul * value);return *this;}template <class RHStype> constexpr modint<modulo>& operator%=(const RHStype rhs) NOEXCEPT {com("[Warning] mint::operator%= : Are you sure you want to do this?");O_assert(rhs != 0);value %= rhs;return *this;}template <class RHStype> constexpr modint<modulo>& operator&=(const RHStype rhs) noexcept {com("[Warning] mint::operator&= : Are you sure you want to do this?");value &= rhs;return *this;}template <class RHStype> constexpr modint<modulo>& operator|=(const RHStype rhs) noexcept {com("[Warning] mint::operator|= : Are you sure you want to do this?");value |= rhs;clamp_self();return *this;}template <class RHStype> constexpr modint<modulo>& operator^=(const RHStype rhs) noexcept {com("[Warning] mint::operator^= : Are you sure you want to do this?");value ^= rhs;clamp_self();return *this;}template <class RHStype> constexpr modint<modulo>& operator<<=(const RHStype rhs) noexcept {com("[Warning] mint::operator<<= : Are you sure you want to do this?");value = clamp_ll(static_cast<long long>(value) << rhs);return *this;}template <class RHStype> constexpr modint<modulo>& operator>>=(const RHStype rhs) noexcept {com("[Warning] mint::operator>>= : Are you sure you want to do this?");value >>= rhs;return *this;}constexpr bool operator!(void) const noexcept {com("[Warning] mint::operator! : Are you sure you want to do this?");return value == 0;}constexpr modint<modulo> operator~(void) const noexcept {com("[Warning] mint::operator~ : Are you sure you want to do this?");return modint<modulo>(~value);}constexpr modint<modulo> operator-(void) const noexcept {return modint<modulo>(value == 0 ? 0 : modulo - value, true);}constexpr modint<modulo> operator+(void) const noexcept {return *this;}constexpr modint<modulo>& operator++(void) noexcept {value = ((value + 1 == modulo) ? 0 : value + 1);return *this;}constexpr modint<modulo>& operator--(void) noexcept {value = ((value == 0) ? modulo - 1 : value - 1);return *this;}constexpr modint<modulo> operator++(int) noexcept {int ret = value;++(*this);return modint<modulo>(ret, true);}constexpr modint<modulo> operator--(int) noexcept {int ret = value;--(*this);return modint<modulo>(ret, true);}constexpr bool operator==(const modint<modulo> rhs) const noexcept {return value == rhs.value;}constexpr bool operator!=(const modint<modulo> rhs) const noexcept {return value != rhs.value;}constexpr bool operator<(const modint<modulo> rhs) const noexcept {com("[Warning] mint::operator< : Are you sure you want to do this?");return value < rhs.value;}constexpr bool operator<=(const modint<modulo> rhs) const noexcept {com("[Warning] mint::operator<= : Are you sure you want to do this?");return value <= rhs.value;}constexpr bool operator>(const modint<modulo> rhs) const noexcept {com("[Warning] mint::operator> : Are you sure you want to do this?");return value > rhs.value;}constexpr bool operator>=(const modint<modulo> rhs) const noexcept {com("[Warning] mint::operator>= : Are you sure you want to do this?");return value >= rhs.value;}constexpr bool operator&&(const modint<modulo> rhs) const noexcept {com("[Warning] mint::operator&& : Are you sure you want to do this?");return value && rhs.value;}constexpr bool operator||(const modint<modulo> rhs) const noexcept {com("[Warning] mint::operator|| : Are you sure you want to do this?");return value || rhs.value;}template <class RHStype> constexpr bool operator==(const RHStype rhs) const noexcept {return value == rhs;}template <class RHStype> constexpr bool operator!=(const RHStype rhs) const noexcept {return value != rhs;}template <class RHStype> constexpr bool operator<(const RHStype rhs) const noexcept {com("[Warning] mint::operator< : Are you sure you want to do this?");return value < rhs;}template <class RHStype> constexpr bool operator<=(const RHStype rhs) const noexcept {com("[Warning] mint::operator<= : Are you sure you want to do this?");return value <= rhs;}template <class RHStype> constexpr bool operator>(const RHStype rhs) const noexcept {com("[Warning] mint::operator> : Are you sure you want to do this?");return value > rhs;}template <class RHStype> constexpr bool operator>=(const RHStype rhs) const noexcept {com("[Warning] mint::operator>= : Are you sure you want to do this?");return value >= rhs;}template <class RHStype> constexpr bool operator&&(const RHStype rhs) const noexcept {com("[Warning] mint::operator&& : Are you sure you want to do this?");return value && rhs;}template <class RHStype> constexpr bool operator||(const RHStype rhs) const noexcept {com("[Warning] mint::operator|| : Are you sure you want to do this?");return value || rhs;}constexpr operator int() const noexcept {return value;}friend std::istream& operator>>(std::istream& is, modint<modulo>& rhs) {long long tmp;is >> tmp;if (tmp < -modulo || modulo <= tmp) tmp %= modulo;if (tmp < 0) tmp += modulo;rhs.value = static_cast<int>(tmp);return is;}friend std::ostream& operator<<(std::ostream& os, modint<modulo>& rhs) {return os << rhs.value;}/* function */constexpr modint<modulo> inv(void) const NOEXCEPT {O_assert(value != 0);return modint<modulo>(calc_inverse(value), true);}constexpr modint<modulo> pow(int index) const noexcept {modint<modulo> ret(1, true), base(value, true);while (index > 0) {if (index & 1) ret *= base;base *= base;index >>= 1;}return ret;}};template <class LHStype, int modulo> constexpr modint<modulo> operator+(const LHStype lhs, const modint<modulo> rhs) noexcept {return rhs + lhs;}template <class LHStype, int modulo> constexpr modint<modulo> operator-(const LHStype lhs, const modint<modulo> rhs) noexcept {return -rhs + lhs;}template <class LHStype, int modulo> constexpr modint<modulo> operator*(const LHStype lhs, const modint<modulo> rhs) noexcept {return rhs * lhs;}template <class LHStype, int modulo> constexpr modint<modulo> operator/(const LHStype lhs, const modint<modulo> rhs) noexcept {return rhs.inv() * lhs;}template <class LHStype, int modulo> constexpr modint<modulo> operator%(const LHStype lhs, const modint<modulo> rhs) noexcept {com("[Warning] operator%<LHStype, mint> : Are you sure you want to do this?");return modint<modulo>(lhs % (int) rhs, true);}template <class LHStype, int modulo, std::enable_if_t<std::is_integral_v<LHStype>, std::nullptr_t> = nullptr> constexpr modint<modulo> operator<<(const LHStype lhs, const modint<modulo> rhs) noexcept {com("[Warning] operator<< <LHStype, mint> : Are you sure you want to do this?");return modint<modulo>(static_cast<long long>(lhs) << (int) rhs);}template <class LHStype, int modulo, std::enable_if_t<std::is_integral_v<LHStype>, std::nullptr_t> = nullptr> constexpr modint<modulo> operator>>(const LHStype lhs, const modint<modulo> rhs) noexcept {com("[Warning] operator>> <LHStype, mint> : Are you sure you want to do this?");return modint<modulo>(lhs >> (int) rhs);}template <class LHStype, int modulo> constexpr LHStype& operator+=(LHStype& lhs, const modint<modulo> rhs) noexcept {return lhs += (int) rhs;}template <class LHStype, int modulo> constexpr LHStype& operator-=(LHStype& lhs, const modint<modulo> rhs) noexcept {return lhs -= (int) rhs;}template <class LHStype, int modulo> constexpr LHStype& operator*=(LHStype& lhs, const modint<modulo> rhs) noexcept {return lhs *= (int) rhs;}template <class LHStype, int modulo> constexpr LHStype& operator/=(LHStype& lhs, const modint<modulo> rhs) noexcept {return lhs /= (int) rhs;}template <class LHStype, int modulo> constexpr LHStype& operator%=(LHStype& lhs, const modint<modulo> rhs) noexcept {com("[Warning] operator%= <LHStype, mint> : Are you sure you want to do this?");return lhs %= (int) rhs;}template <class LHStype, int modulo> constexpr LHStype& operator&=(LHStype& lhs, const modint<modulo> rhs) noexcept {com("[Warning] operator&= <LHStype, mint> : Are you sure you want to do this?");return lhs &= (int) rhs;}template <class LHStype, int modulo> constexpr LHStype& operator|=(LHStype& lhs, const modint<modulo> rhs) noexcept {com("[Warning] operator|= <LHStype, mint> : Are you sure you want to do this?");return lhs |= (int) rhs;}template <class LHStype, int modulo> constexpr LHStype& operator^=(LHStype& lhs, const modint<modulo> rhs) noexcept {com("[Warning] operator^= <LHStype, mint> : Are you sure you want to do this?");return lhs ^= (int) rhs;}template <class LHStype, int modulo> constexpr LHStype& operator<<=(LHStype& lhs, const modint<modulo> rhs) noexcept {com("[Warning] operator<<= <LHStype, mint> : Are you sure you want to do this?");return lhs <<= (int) rhs;}template <class LHStype, int modulo> constexpr LHStype& operator>>=(LHStype& lhs, const modint<modulo> rhs) noexcept {com("[Warning] operator>>= <LHStype, mint> : Are you sure you want to do this?");return lhs >>= (int) rhs;}} // namespace libusing mint = lib::modint<MOD>;template <class T> struct std::common_type<mint, T> { using type = mint; };template <class T> struct std::common_type<T, mint> { using type = mint; };#endif#pragma endregion#pragma region lib_binary_indexed_treenamespace lib {/* Checked on 2020-09-21 https://atcoder.jp/contests/practice2/submissions/16926123 *//*class BinaryIndexedTreeusage: BinaryIndexedTree f(100), BinaryIndexedTree<long long> f(100)*/template <class T = int> class BinaryIndexedTree {public:int size;BinaryIndexedTree() {}BinaryIndexedTree(int s) :size(s), data(s + 1, (T) 0) {}BinaryIndexedTree(int s, const T& v) {size = s;data = std::vector<T>(s + 1);for (int i = 0; i < s; i++) add(i, v);}BinaryIndexedTree(const vector<T>& d) {size = d.size();data = std::vector<T>(size + 1, (T) 0);for (int i = 0; i < size; i++) add(i, d[i]);}void add(int idx, const T& diff) {for (idx++; idx <= size; idx += (idx & -idx)) {data[idx] += diff;}}/* sum of the interval [0, idx] (inclusive, 0-indexed) */T sum(int idx) {if (idx < 0) return 0;T ret = 0;for (idx++; idx > 0; idx -= (idx & -idx)) {ret += data[idx];}return ret;}/* sum of the interval [l, r] (inclusive, 0-indexed) */T sum(int l, int r) {return sum(r) - sum(l - 1);}T get(int idx) {return sum(idx) - sum(idx - 1);}T all_sum() {return sum(size - 1);}private:std::vector<T> data;};template <class T = int> class BinaryIndexedTree_RAQ {public:int size;BinaryIndexedTree_RAQ() {}BinaryIndexedTree_RAQ(int s) :size(s), BIT_0(s), BIT_1(s) {}BinaryIndexedTree_RAQ(int s, const T& v) :size(s), BIT_0(s, v), BIT_1(s) {}BinaryIndexedTree_RAQ(const std::vector<T>& d) :size(static_cast<int>(d.size())), BIT_0(d), BIT_1(static_cast<int>(d.size())) {}void add(int idx, const T& diff) {add(idx, idx, diff);}/* interval [l, r] (inclusive, 0-indexed) */void add(int l, int r, const T& diff) {BIT_0.add(l, diff * -1 * (l - 1));BIT_0.add(r + 1, diff * r);BIT_1.add(l, diff);BIT_1.add(r + 1, diff * -1);}/* sum of the interval [0, idx] (inclusive, 0-indexed) */T sum(int idx) {if (idx < 0) return 0;return BIT_0.sum(idx) + BIT_1.sum(idx) * idx;}/* sum of the interval [l, r] (inclusive, 0-indexed) */T sum(int l, int r) {return sum(r) - sum(l - 1);}T get(int idx) {return sum(idx) - sum(idx - 1);}T all_sum() {return sum(size - 1);}void all_add(const T& diff) {add(0, size - 1, diff);}private:BinaryIndexedTree<T> BIT_0;BinaryIndexedTree<T> BIT_1;};template <class T> std::ostream& operator<<(std::ostream& os, BinaryIndexedTree<T>& f) {os << "val [ ";for (int i = 0; i < f.size; i++) os << f.get(i) << " ";os << "]\n"<< "sum [ ";for (int i = 0; i < f.size; i++) os << f.sum(i) << " ";return os << "]\n";}template <class T> std::ostream& operator<<(std::ostream& os, BinaryIndexedTree_RAQ<T>& f) {os << "val [ ";for (int i = 0; i < f.size; i++) os << f.get(i) << " ";os << "]\n"<< "sum [ ";for (int i = 0; i < f.size; i++) os << f.sum(i) << " ";return os << "]\n";}} // namespace lib#pragma endregionvoid solve() {int N;scanf("%d", &N);vector<int> A(N);std::map<int, int> cnt;rep(i, A.size()) {std::cin >> A[i];cnt[A[i]]++;}vector<std::pair<int, int>> L, R;for (auto&& p : cnt) {L.emplace_back(p);R.emplace_back(p);}std::sort(L.begin(), L.end());std::sort(R.rbegin(), R.rend());int M = (int) L.size();// vector<long long> L_acc(M), R_acc(M);// vector<int> L_cntacc(M), R_cntacc(M);lib::BinaryIndexedTree<mint> Lacc(M), Racc(M);lib::BinaryIndexedTree<mint> Lcnt(M), Rcnt(M);rep(i, M) {// L_acc[i] = L[i].first * L[i].second;// R_acc[i] = R[i].first * R[i].second;// L_cntacc[i] = L[i].second;// R_cntacc[i] = R[i].second;// if (i > 0) {// L_acc[i] += L_acc[i - 1];// R_acc[i] += R_acc[i - 1];// L_cntacc[i] += L_acc[i - 1];// R_cntacc[i] += L_acc[i - 1];// }Lacc.add(i, L[i].first * L[i].second);Racc.add(i, R[i].first * R[i].second);Lcnt.add(i, L[i].second);Rcnt.add(i, R[i].second);}vector<mint> right(N), left(N);vector<int> rs(N), ls(N);rep(i, N - 1) {int idx = (int) std::distance(L.begin(), std::lower_bound(L.begin(), L.end(), std::pair<int, int>(A[i], 0)));// L[idx].second--;// L_acc[i] -= A[i];// L_cntacc[i]--;Lacc.add(idx, -A[i]);Lcnt.add(idx, -1);see(i, A[i], L, idx);if (i == 0) continue;if (idx == 0) continue;right[i] = Lacc.sum(idx - 1);rs[i] = Lcnt.sum(idx - 1);// see(right[i], rs[i]);}com("==========\n\n");rep(i, N - 1) {int idx = (int) std::distance(std::lower_bound(R.rbegin(), R.rend(), std::pair<int, int>(A[N - 1 - i], 0)), R.rend()) - 1;R[idx].second--;Racc.add(idx, -A[N - 1 - i]);Rcnt.add(idx, -1);see(i, A[i], R, idx);if (i == 0) continue;if (idx == 0) continue;left[i] = Racc.sum(idx - 1);ls[i] = Rcnt.sum(idx - 1);// see(left[i], ls[i]);}com("==========\n\n");see(right, rs, left, ls);std::reverse(left.begin(), left.end());std::reverse(ls.begin(), ls.end());mint ans = 0;for (int i = 1; i < N - 1; i++) {// ans += mint(right[i]) * left[i] + mint(A[i]) * rs[i] * ls[i];ans += mint(right[i]) * ls[i];ans += mint(left[i]) * rs[i];ans += mint(A[i]) * rs[i] * ls[i];}std::cout << ans << "\n";}int main() {solve();}