結果
| 問題 |
No.2950 Max Min Product
|
| コンテスト | |
| ユーザー |
 kk2a
|
| 提出日時 | 2024-10-27 13:25:12 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,179 ms / 3,000 ms |
| コード長 | 32,455 bytes |
| コンパイル時間 | 3,402 ms |
| コンパイル使用メモリ | 228,660 KB |
| 実行使用メモリ | 24,416 KB |
| 最終ジャッジ日時 | 2024-10-27 13:25:46 |
| 合計ジャッジ時間 | 33,441 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 |
ソースコード
#ifndef MODINT_HPP
#define MODINT_HPP 1
#include <cassert>
#include <iostream>
#include <type_traits>
#include <utility>
#ifndef TYPE_TRAITS_HPP
#define TYPE_TRAITS_HPP 1
#include <istream>
#include <ostream>
#include <type_traits>
namespace kk2 {
template <typename T>
using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value
or std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value
or std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_integral =
typename std::conditional<std::is_integral<T>::value or is_signed_int128<T>::value
or is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_signed = typename std::conditional<std::is_signed<T>::value or is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_unsigned =
typename std::conditional<std::is_unsigned<T>::value or is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;
template <typename T>
using to_unsigned =
typename std::conditional<is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
template <typename T> using is_integral_t = std::enable_if_t<is_integral<T>::value>;
template <typename T> using is_signed_t = std::enable_if_t<is_signed<T>::value>;
template <typename T> using is_unsigned_t = std::enable_if_t<is_unsigned<T>::value>;
template <typename T>
using is_function_pointer =
typename std::conditional<std::is_pointer_v<T> && std::is_function_v<std::remove_pointer_t<T>>,
std::true_type,
std::false_type>::type;
template <typename T, std::enable_if_t<is_function_pointer<T>::value> * = nullptr>
struct is_two_args_function_pointer : std::false_type {};
template <typename R, typename T1, typename T2>
struct is_two_args_function_pointer<R (*)(T1, T2)> : std::true_type {};
template <typename T>
using is_two_args_function_pointer_t = std::enable_if_t<is_two_args_function_pointer<T>::value>;
namespace type_traits {
struct istream_tag {};
struct ostream_tag {};
} // namespace type_traits
template <typename T> using is_standard_istream = std::is_same<T, std::istream>;
template <typename T> using is_standard_ostream = std::is_same<T, std::ostream>;
template <typename T> using is_user_defined_istream = std::is_base_of<type_traits::istream_tag, T>;
template <typename T> using is_user_defined_ostream = std::is_base_of<type_traits::ostream_tag, T>;
template <typename T>
using is_istream =
typename std::conditional<is_standard_istream<T>::value || is_user_defined_istream<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_ostream =
typename std::conditional<is_standard_ostream<T>::value || is_user_defined_ostream<T>::value,
std::true_type,
std::false_type>::type;
template <typename T> using is_istream_t = std::enable_if_t<is_istream<T>::value>;
template <typename T> using is_ostream_t = std::enable_if_t<is_ostream<T>::value>;
} // namespace kk2
#endif // TYPE_TRAITS_HPP
// #include "../type_traits/type_traits.hpp"
namespace kk2 {
template <int p> struct ModInt {
using mint = ModInt;
public:
static int Mod;
constexpr static unsigned int getmod() {
if (p > 0) return p;
else return Mod;
}
static void setmod(int Mod_) {
assert(1 <= Mod_);
Mod = Mod_;
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
constexpr ModInt() : _v(0) {}
template <class T, is_integral_t<T> * = nullptr> constexpr ModInt(T v) {
if constexpr (is_signed<T>::value) {
v %= getmod();
if (v < 0) v += getmod();
_v = v;
} else if constexpr (is_unsigned<T>::value) {
_v = v %= getmod();
} else {
ModInt();
}
}
unsigned int val() const { return _v; }
mint &operator++() {
_v++;
if (_v == getmod()) _v = 0;
return *this;
}
mint &operator--() {
if (_v == 0) _v = getmod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint &operator+=(const mint &rhs) {
_v += rhs._v;
if (_v >= getmod()) _v -= getmod();
return *this;
}
mint &operator-=(const mint &rhs) {
_v += getmod() - rhs._v;
if (_v >= getmod()) _v -= getmod();
return *this;
}
mint &operator*=(const mint &rhs) {
unsigned long long z = _v;
z *= rhs._v;
z %= getmod();
_v = z;
return *this;
}
mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
long long s = getmod(), t = _v;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u;
std::swap(s, t);
std::swap(m0, m1);
}
if (m0 < 0) m0 += getmod() / s;
return m0;
}
friend mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
friend mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
friend mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
friend mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
friend bool operator==(const mint &lhs, const mint &rhs) { return lhs._v == rhs._v; }
friend bool operator!=(const mint &lhs, const mint &rhs) { return lhs._v != rhs._v; }
template <class OStream, is_ostream_t<OStream> * = nullptr>
friend OStream &operator<<(OStream &os, const mint &mint_) {
os << mint_._v;
return os;
}
template <class IStream, is_istream_t<IStream> * = nullptr>
friend IStream &operator>>(IStream &is, mint &mint_) {
long long x;
is >> x;
mint_ = mint(x);
return is;
}
private:
unsigned int _v;
};
template <int p> int ModInt<p>::Mod = 998244353;
using mint998 = ModInt<998244353>;
using mint107 = ModInt<1000000007>;
} // namespace kk2
#endif // MODINT_HPP
// #include <kk2/modint/modint.hpp>
#ifndef LAZY_HPP
#define LAZY_HPP 1
#include <cassert>
#include <functional>
#include <vector>
namespace kk2 {
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct LazySegTree {
public:
LazySegTree() : LazySegTree(0) {}
LazySegTree(int n) : LazySegTree(std::vector<S>(n, e())) {}
template <class... Args>
LazySegTree(int n, Args... args) : LazySegTree(std::vector<S>(n, S(args...))) {}
LazySegTree(const std::vector<S> &v) : _n(int(v.size())) {
log = 0;
while ((1ll << log) < _n) log++;
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) { update(i); }
}
using Monoid = S;
static S Op(S l, S r) { return op(l, r); }
static S MonoidUnit() { return e(); }
using Hom = F;
static S Map(F f, S x) { return mapping(f, x); }
static F Composition(F l, F r) { return composition(l, r); }
static F HomUnit() { return id(); }
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
template <class... Args> void emplace_set(int p, Args... args) { set(p, S(args...)); }
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push(r >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
template <class... Args> void emplace_apply_point(int p, Args... args) { apply(p, F(args...)); }
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <class... Args> void emplace_apply_range(int l, int r, Args... args) {
apply(l, r, F(args...));
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
} // namespace kk2
#endif // LAZY_HPP
// #include <kk2/segment_tree/lazy.hpp>
#ifndef SEGMENT_TREE_UTILITY_UPDATEMAX_HPP
#define SEGMENT_TREE_UTILITY_UPDATEMAX_HPP 1
#ifndef MATH_HOMOMORPHISM_UPDATE_HPP
#define MATH_HOMOMORPHISM_UPDATE_HPP 1
#include <iostream>
namespace kk2 {
namespace homomorphism {
template <class S> struct Update {
S a;
bool id;
constexpr Update() : a(S()), id(true) {}
constexpr Update(S a_, bool id_ = false) : a(a_), id(id_) {}
operator S() const { return a; }
template <class OStream>
friend OStream &operator<<(OStream &os, const Update &update) {
if (update.id) os << "id";
else os << update.a;
return os;
}
};
template <class S, class T> constexpr T UpdateMap(Update<S> f, T x) {
return f.id ? x : x.update(f.a);
}
template <class S> constexpr Update<S> UpdateComposition(Update<S> l, Update<S> r) {
if (l.id) return r;
return l;
}
template <class S> Update<S> UpdateUnit() {
constexpr static Update<S> e = Update<S>();
return e;
}
} // namespace homomorphism
} // namespace kk2
#endif // MATH_HOMOMORPHISM_UPDATE_HPP
// #include "../../math/homomorphism/update.hpp"
#ifndef MATH_MONOID_MAX_HPP
#define MATH_MONOID_MAX_HPP 1
#include <algorithm>
#include <iostream>
#include <vector>
namespace kk2 {
namespace monoid {
template <class S> struct Max {
S a;
bool minf;
constexpr Max() : a(S()), minf(true) {}
constexpr Max(S a_, bool minf_ = false) : a(a_), minf(minf_) {}
operator S() const { return a; }
template <class OStream>
friend OStream &operator<<(OStream &os, const Max &max) {
if (max.minf) os << "minf";
else os << max.a;
return os;
}
template <class IStream>
friend IStream &operator>>(IStream &is, Max &max) {
is >> max.a;
max.minf = false;
return is;
}
constexpr Max &operator=(const S &rhs) {
a = rhs;
minf = false;
return *this;
}
constexpr Max &add(const S &rhs) {
if (minf) return *this;
a += rhs;
return *this;
}
constexpr Max &update(const S &rhs) {
a = rhs;
minf = false;
return *this;
}
constexpr bool is_minf() { return minf; }
};
template <class S> constexpr Max<S> MaxOp(Max<S> l, Max<S> r) {
if (r.minf) return l;
if (l.minf) return r;
l.a = std::max(l.a, r.a);
return l;
}
template <class S> Max<S> MaxUnit() {
constexpr static Max<S> e = Max<S>();
return e;
}
} // namespace monoid
template <class S, class... Args>
std::vector<monoid::Max<S>> GetVecMax(int n, Args... args) {
return std::vector<monoid::Max<S>>(n, monoid::Max<S>(args...));
}
template <class S, class... Args>
std::vector<std::vector<monoid::Max<S>>> GetVecMax2D(int h, int w, Args... args) {
return std::vector<std::vector<monoid::Max<S>>>(h, GetVecMax<S>(w, args...));
}
} // namespace kk2
#endif // MATH_MONOID_MAX_H
// #include "../../math/monoid/max.hpp"
// #include "../lazy.hpp"
namespace kk2 {
template <class S>
using UpdateMax = LazySegTree<monoid::Max<S>,
monoid::MaxOp<S>,
monoid::MaxUnit<S>,
homomorphism::Update<S>,
homomorphism::UpdateMap<S, monoid::Max<S>>,
homomorphism::UpdateComposition<S>,
homomorphism::UpdateUnit<S>>;
} // namespace kk2
#endif // SEGMENT_TREE_UTILITY_UPDATEMAX_HPP
// #include <kk2/segment_tree/utility/updatemax.hpp>
#ifndef TEMPLATE
#define TEMPLATE 1
// #pragma GCC optimize("O3,unroll-loops")
// #include <bits/stdc++.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// #include "../type_traits/type_traits.hpp"
#ifndef TEMPLATE_FASTIO_HPP
#define TEMPLATE_FASTIO_HPP 1
#include <cctype>
#include <cstdint>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <string>
// #include "../type_traits/type_traits.hpp"
namespace kk2 {
namespace fastio {
#define INPUT_FILE "in.txt"
#define OUTPUT_FILE "out.txt"
struct Scanner : type_traits::istream_tag {
private:
static constexpr size_t INPUT_BUF = 1 << 17;
size_t pos = 0, end = 0;
static char buf[INPUT_BUF];
FILE *fp;
public:
Scanner() : fp(stdin) {}
Scanner(const char *file) : fp(fopen(file, "r")) {}
~Scanner() {
if (fp != stdin) fclose(fp);
}
char now() {
if (pos == end) {
while (!(end = fread(buf, 1, INPUT_BUF, fp))) {}
if (end != INPUT_BUF) buf[end] = '\0';
pos = 0;
}
return buf[pos];
}
void skip_space() {
while (isspace(now())) ++pos;
}
template <class T, is_unsigned_t<T> * = nullptr> T next_unsigned_integral() {
skip_space();
T res{};
while (isdigit(now())) {
res = res * 10 + (now() - '0');
++pos;
}
return res;
}
template <class T, is_signed_t<T> * = nullptr> T next_signed_integral() {
skip_space();
if (now() == '-') {
++pos;
return T(-next_unsigned_integral<typename to_unsigned<T>::type>());
} else return (T)next_unsigned_integral<typename to_unsigned<T>::type>();
}
char next_char() {
skip_space();
auto res = now();
++pos;
return res;
}
std::string next_string() {
skip_space();
std::string res;
while (true) {
char c = now();
if (isspace(c) or c == '\0') break;
res.push_back(now());
++pos;
}
return res;
}
template <class T, is_unsigned_t<T> * = nullptr> Scanner &operator>>(T &x) {
x = next_unsigned_integral<T>();
return *this;
}
template <class T, is_signed_t<T> * = nullptr> Scanner &operator>>(T &x) {
x = next_signed_integral<T>();
return *this;
}
Scanner &operator>>(char &x) {
x = next_char();
return *this;
}
Scanner &operator>>(std::string &x) {
x = next_string();
return *this;
}
};
struct endl_struct_t {};
struct Printer : type_traits::ostream_tag {
private:
static char helper[10000][5];
static char leading_zero[10000][5];
constexpr static size_t OUTPUT_BUF = 1 << 17;
static char buf[OUTPUT_BUF];
size_t pos = 0;
FILE *fp;
template <class T> static constexpr void div_mod(T &a, T &b, T mod) {
a = b / mod;
b -= a * mod;
}
static void init() {
buf[0] = '\0';
for (size_t i = 0; i < 10000; ++i) {
leading_zero[i][0] = i / 1000 + '0';
leading_zero[i][1] = i / 100 % 10 + '0';
leading_zero[i][2] = i / 10 % 10 + '0';
leading_zero[i][3] = i % 10 + '0';
leading_zero[i][4] = '\0';
size_t j = 0;
if (i >= 1000) helper[i][j++] = i / 1000 + '0';
if (i >= 100) helper[i][j++] = i / 100 % 10 + '0';
if (i >= 10) helper[i][j++] = i / 10 % 10 + '0';
helper[i][j++] = i % 10 + '0';
helper[i][j] = '\0';
}
}
public:
Printer() : fp(stdout) { init(); }
Printer(const char *file) : fp(fopen(file, "w")) { init(); }
~Printer() {
write();
if (fp != stdout) fclose(fp);
}
void write() {
fwrite(buf, 1, pos, fp);
pos = 0;
}
void flush() {
write();
fflush(fp);
}
void put_char(char c) {
if (pos == OUTPUT_BUF) write();
buf[pos++] = c;
}
void put_cstr(const char *s) {
while (*s) put_char(*(s++));
}
void put_u32(uint32_t x) {
uint32_t y;
if (x >= 100000000) { // 10^8
div_mod<uint32_t>(y, x, 100000000);
put_cstr(helper[y]);
div_mod<uint32_t>(y, x, 10000);
put_cstr(leading_zero[y]);
put_cstr(leading_zero[x]);
} else if (x >= 10000) { // 10^4
div_mod<uint32_t>(y, x, 10000);
put_cstr(helper[y]);
put_cstr(leading_zero[x]);
} else put_cstr(helper[x]);
}
void put_i32(int32_t x) {
if (x < 0) {
put_char('-');
put_u32(-x);
} else put_u32(x);
}
void put_u64(uint64_t x) {
uint64_t y;
if (x >= 1000000000000ull) { // 10^12
div_mod<uint64_t>(y, x, 1000000000000ull);
put_u32(y);
div_mod<uint64_t>(y, x, 100000000ull);
put_cstr(leading_zero[y]);
div_mod<uint64_t>(y, x, 10000ull);
put_cstr(leading_zero[y]);
put_cstr(leading_zero[x]);
} else if (x >= 10000ull) { // 10^4
div_mod<uint64_t>(y, x, 10000ull);
put_u32(y);
put_cstr(leading_zero[x]);
} else put_cstr(helper[x]);
}
void put_i64(int64_t x) {
if (x < 0) {
put_char('-');
put_u64(-x);
} else put_u64(x);
}
void put_u128(__uint128_t x) {
constexpr static __uint128_t pow10_10 = 10000000000ull;
constexpr static __uint128_t pow10_20 = pow10_10 * pow10_10;
__uint128_t y;
if (x >= pow10_20) { // 10^20
div_mod<__uint128_t>(y, x, pow10_20);
put_u64(uint64_t(y));
div_mod<__uint128_t>(y, x, __uint128_t(10000000000000000ull));
put_cstr(leading_zero[y]);
div_mod<__uint128_t>(y, x, __uint128_t(1000000000000ull));
put_cstr(leading_zero[y]);
div_mod<__uint128_t>(y, x, __uint128_t(100000000ull));
put_cstr(leading_zero[y]);
div_mod<__uint128_t>(y, x, __uint128_t(10000ull));
put_cstr(leading_zero[y]);
put_cstr(leading_zero[x]);
} else if (x >= __uint128_t(10000)) { // 10^4
div_mod<__uint128_t>(y, x, __uint128_t(10000));
put_u64(uint64_t(y));
put_cstr(leading_zero[x]);
} else put_cstr(helper[x]);
}
void put_i128(__int128_t x) {
if (x < 0) {
put_char('-');
put_u128(-x);
} else put_u128(x);
}
template <class T, is_unsigned_t<T> * = nullptr> Printer &operator<<(T x) {
if constexpr (sizeof(T) <= 4) put_u32(x);
else if constexpr (sizeof(T) <= 8) put_u64(x);
else put_u128(x);
return *this;
}
template <class T, is_signed_t<T> * = nullptr> Printer &operator<<(T x) {
if constexpr (sizeof(T) <= 4) put_i32(x);
else if constexpr (sizeof(T) <= 8) put_i64(x);
else put_i128(x);
return *this;
}
Printer &operator<<(char x) {
put_char(x);
return *this;
}
Printer &operator<<(const std::string &x) {
for (char c : x) put_char(c);
return *this;
}
Printer &operator<<(const char *x) {
put_cstr(x);
return *this;
}
// std::cout << std::endl; は関数ポインタを渡しているらしい
Printer &operator<<(endl_struct_t) {
put_char('\n');
flush();
return *this;
}
};
char Scanner::buf[Scanner::INPUT_BUF];
char Printer::buf[Printer::OUTPUT_BUF];
char Printer::helper[10000][5];
char Printer::leading_zero[10000][5];
} // namespace fastio
#if defined(INTERACTIVE) || defined(USE_STDIO)
auto &kin = std::cin;
auto &kout = std::cout;
auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>;
#elif defined(KK2)
fastio::Scanner kin(INPUT_FILE);
fastio::Printer kout(OUTPUT_FILE);
fastio::endl_struct_t kendl;
#else
fastio::Scanner kin;
fastio::Printer kout;
fastio::endl_struct_t kendl;
#endif
} // namespace kk2
#endif // TEMPLATE_FASTIO_HPP
// #include "fastio.hpp"
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pi = std::pair<int, int>;
using pl = std::pair<i64, i64>;
using pil = std::pair<int, i64>;
using pli = std::pair<i64, int>;
template <class T> using vc = std::vector<T>;
template <class T> using vvc = std::vector<vc<T>>;
template <class T> using vvvc = std::vector<vvc<T>>;
template <class T> using vvvvc = std::vector<vvvc<T>>;
template <class T> using pq = std::priority_queue<T>;
template <class T> using pqi = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T> constexpr T infty = 0;
template <> constexpr int infty<int> = (1 << 30) - 123;
template <> constexpr i64 infty<i64> = (1ll << 62) - (1ll << 31);
template <> constexpr i128 infty<i128> = (i128(1) << 126) - (i128(1) << 63);
template <> constexpr u32 infty<u32> = infty<int>;
template <> constexpr u64 infty<u64> = infty<i64>;
template <> constexpr u128 infty<u128> = infty<i128>;
template <> constexpr double infty<double> = infty<i64>;
template <> constexpr long double infty<long double> = infty<i64>;
constexpr int mod = 998244353;
constexpr int modu = 1e9 + 7;
constexpr long double PI = 3.14159265358979323846;
namespace kk2 {
template <class T, class... Sizes> auto make_vector(int first, Sizes... sizes) {
if constexpr (sizeof...(sizes) == 0) {
return std::vector<T>(first);
} else {
return std::vector<decltype(make_vector(sizes...))>(first, make_vector(sizes...));
}
}
template <class T, class U> void fill_all(std::vector<T> &v, const U &x) {
std::fill(std::begin(v), std::end(v), T(x));
}
template <class T, class U> void fill_all(std::vector<std::vector<T>> &v, const U &x) {
for (auto &u : v) fill_all(u, x);
}
} // namespace kk2
template <class T, class S> inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S> inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
#define rep1(a) for (i64 _ = 0; _ < (i64)(a); ++_)
#define rep2(i, a) for (i64 i = 0; i < (i64)(a); ++i)
#define rep3(i, a, b) for (i64 i = (a); i < (i64)(b); ++i)
#define repi2(i, a) for (i64 i = (a) - 1; i >= 0; --i)
#define repi3(i, a, b) for (i64 i = (a) - 1; i >= (i64)(b); --i)
#define overload3(a, b, c, d, ...) d
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__)
#define fi first
#define se second
#define all(p) std::begin(p), std::end(p)
using kk2::kendl;
using kk2::kin;
using kk2::kout;
struct IoSetUp {
IoSetUp() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
}
} iosetup;
template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::pair<T, U> &p) {
os << p.first << ' ' << p.second;
return os;
}
template <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::pair<T, U> &p) {
is >> p.first >> p.second;
return is;
}
template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 == (int)v.size() ? "" : " "); }
return os;
}
template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::vector<T> &v) {
for (auto &x : v) is >> x;
return is;
}
void Yes(bool b = 1) {
kout << (b ? "Yes\n" : "No\n");
}
void No(bool b = 1) {
kout << (b ? "No\n" : "Yes\n");
}
void YES(bool b = 1) {
kout << (b ? "YES\n" : "NO\n");
}
void NO(bool b = 1) {
kout << (b ? "NO\n" : "YES\n");
}
void yes(bool b = 1) {
kout << (b ? "yes\n" : "no\n");
}
void no(bool b = 1) {
kout << (b ? "no\n" : "yes\n");
}
#endif // TEMPLATE
// #include <kk2/template/template.hpp>
using namespace std;
struct S {
int a, b;
kk2::mint998 sum_a, sum_b, sum_ab;
int size;
};
S op(S l, S r) {
l.sum_a += r.sum_a;
l.sum_b += r.sum_b;
l.sum_ab += r.sum_ab;
l.size += r.size;
return l;
}
S e() {
return S{0, 0, 0, 0, 0, 0};
}
struct F {
int upd_a, upd_b;
bool unit_a, unit_b;
};
S mapping(F f, S x) {
if (f.unit_a and f.unit_b) return x;
else if (f.unit_a) {
x.b = f.upd_b;
x.sum_b = i64(x.b) * x.size;
x.sum_ab = x.sum_a * x.b;
return x;
}
else if (f.unit_b) {
x.a = f.upd_a;
x.sum_a = i64(x.a) * x.size;
x.sum_ab = x.sum_b * x.a;
return x;
}
else {
x.a = f.upd_a;
x.b = f.upd_b;
x.sum_a = i64(x.a) * x.size;
x.sum_b = i64(x.b) * x.size;
x.sum_ab = kk2::mint998(x.a) * x.b * x.size;
return x;
}
}
F composition(F l, F r) {
if (l.unit_a) {
l.upd_a = r.upd_a;
l.unit_a = r.unit_a;
}
if (l.unit_b) {
l.upd_b = r.upd_b;
l.unit_b = r.unit_b;
}
return l;
}
F id() {
return F{0, 0, true, true};
}
void solve() {
int n;
kin >> n;
vc<int> a(n);
kin >> a;
kk2::LazySegTree<S, op, e, F, mapping, composition, id> seg(n);
kk2::mint998 res = 0, sum = 0;
rep (i, n) {
if (i == 0) {
sum += 1ll * a[i] * a[i];
res += sum;
seg.set(i, S{a[i], a[i], a[i], a[i], 1ll * a[i] * a[i], 1});
continue;
}
if (a[i] > a[i - 1]) {
int idx = seg.min_left(i, [&](S x) -> bool {
if (!x.size) return true;
return x.a < a[i];
});
sum -= seg.prod(idx, i).sum_ab;
seg.apply(idx, i, F{a[i], 0, false, true});
seg.set(i, S{a[i], a[i], a[i], a[i], 1ll * a[i] * a[i], 1});
sum += seg.prod(idx, i + 1).sum_ab;
res += sum;
}
else {
int idx = seg.min_left(i, [&](S x) -> bool {
if (!x.size) return true;
return x.b > a[i];
});
sum -= seg.prod(idx, i).sum_ab;
seg.apply(idx, i, F{0, a[i], true, false});
seg.set(i, S{a[i], a[i], a[i], a[i], 1ll * a[i] * a[i], 1});
sum += seg.prod(idx, i + 1).sum_ab;
res += sum;
}
// rep (j, i + 1) {
// S s = seg.get(j);
// kout << s.a << " " << s.b << " " << s.sum_ab << " " << s.size << kendl;
// }
// kout << res << kendl;
}
kout << res << kendl;
}
int main() {
int t = 1;
// kin >> t;
rep (t) solve();
return 0;
}
// converted!!