#1080031 (C++23) No.3129 Multiple of Twin Subarray

提出ソース
結果

問題	No.3129 Multiple of Twin Subarray
コンテスト
ユーザー	kk2a
提出日時	2025-04-25 22:07:31
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	751 ms / 2,000 ms
コード長	42,166 bytes
コンパイル時間	1,764 ms
コンパイル使用メモリ	146,952 KB
実行使用メモリ	30,700 KB
最終ジャッジ日時	2025-04-25 22:08:02
合計ジャッジ時間	23,607 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 46
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <istream>
#include <stack>
#include <iterator>
#include <utility>
#include <cassert>
#include <array>
#include <optional>
#include <algorithm>
#include <fstream>
#include <bitset>
#include <ostream>
#include <iostream>
#include <type_traits>
#include <map>
#include <numeric>
#include <string>
#include <functional>
#include <unordered_set>
#include <vector>
#include <deque>
#include <queue>
#include <iomanip>
#include <set>
#include <unordered_map>

#ifndef KK2_TEMPLATE_PROCON_HPP
#define KK2_TEMPLATE_PROCON_HPP 1


#ifndef KK2_TEMPLATE_CONSTANT_HPP
#define KK2_TEMPLATE_CONSTANT_HPP 1

#ifndef KK2_TEMPLATE_TYPE_ALIAS_HPP
#define KK2_TEMPLATE_TYPE_ALIAS_HPP 1


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>>;

#endif // KK2_TEMPLATE_TYPE_ALIAS_HPP

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;

#endif // KK2_TEMPLATE_CONSTANT_HPP
#ifndef KK2_TEMPLATE_FUNCTION_UTIL_HPP
#define KK2_TEMPLATE_FUNCTION_UTIL_HPP 1


#ifndef KK2_MATH_MONOID_MAX_HPP
#define KK2_MATH_MONOID_MAX_HPP 1


#ifndef KK2_TYPE_TRAITS_IO_HPP
#define KK2_TYPE_TRAITS_IO_HPP 1



namespace kk2 {

namespace type_traits {

struct istream_tag {};
struct ostream_tag {};

} // namespace type_traits

template <typename T> using is_standard_istream =
    typename std::conditional<std::is_same<T, std::istream>::value
                                  || std::is_same<T, std::ifstream>::value,
                              std::true_type,
                              std::false_type>::type;
template <typename T> using is_standard_ostream =
    typename std::conditional<std::is_same<T, std::ostream>::value
                                  || std::is_same<T, std::ofstream>::value,
                              std::true_type,
                              std::false_type>::type;
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 // KK2_TYPE_TRAITS_IO_HPP

namespace kk2 {

namespace monoid {

template <class S, class Compare = std::less<S>> struct Max {
    static constexpr bool commutative = true;
    using M = Max;
    S a;
    bool is_unit;

    Max() : a(S()), is_unit(true) {}
    Max(S a_) : a(a_), is_unit(false) {}
    operator S() const { return a; }

    inline static M op(M l, M r) {
        if (l.is_unit or r.is_unit) return l.is_unit ? r : l;
        return Compare{}(l.a, r.a) ? r : l;
    }

    inline static M unit() { return M(); }

    bool operator==(const M &rhs) const {
        return is_unit == rhs.is_unit and (is_unit or a == rhs.a);
    }

    bool operator!=(const M &rhs) const {
        return is_unit != rhs.is_unit or (!is_unit and a != rhs.a);
    }

    template <class OStream, is_ostream_t<OStream> * = nullptr>
    friend OStream &operator<<(OStream &os, const M &x) {
        if (x.is_unit) os << "-inf";
        else os << x.a;
        return os;
    }

    template <class IStream, is_istream_t<IStream> * = nullptr>
    friend IStream &operator>>(IStream &is, M &x) {
        is >> x.a;
        x.is_unit = false;
        return is;
    }
};

} // namespace monoid

} // namespace kk2

#endif // MATH_MONOID_MAX_HPP
#ifndef KK2_MATH_MONOID_MIN_HPP
#define KK2_MATH_MONOID_MIN_HPP 1



namespace kk2 {

namespace monoid {

template <class S, class Compare = std::less<S>> struct Min {
    static constexpr bool commutative = true;
    using M = Min;
    S a;
    bool is_unit;

    Min() : a(S()), is_unit(true) {}
    Min(S a_) : a(a_), is_unit(false) {}
    operator S() const { return a; }

    inline static M op(M l, M r) {
        if (l.is_unit or r.is_unit) return l.is_unit ? r : l;
        return Compare{}(l.a, r.a) ? l : r;
    }

    inline static M unit() { return M(); }

    bool operator==(const M &rhs) const {
        return is_unit == rhs.is_unit and (is_unit or a == rhs.a);
    }

    bool operator!=(const M &rhs) const {
        return is_unit != rhs.is_unit or (!is_unit and a != rhs.a);
    }

    template <class OStream, is_ostream_t<OStream> * = nullptr>
    friend OStream &operator<<(OStream &os, const M &x) {
        if (x.is_unit) os << "inf";
        else os << x.a;
        return os;
    }

    template <class IStream, is_istream_t<IStream> * = nullptr>
    friend IStream &operator>>(IStream &is, M &x) {
        is >> x.a;
        x.is_unit = false;
        return is;
    }
};

} // namespace monoid

} // namespace kk2

#endif // KK2_MATH_MONOID_MIN_HPP
#ifndef KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP
#define KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP 1



namespace kk2 {

template <typename T> struct is_vector : std::false_type {};
template <typename T, typename Alloc> struct is_vector<std::vector<T, Alloc>> : std::true_type {};

} // namespace kk2

#endif // KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP

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<T>(sizes...))>(first, make_vector<T>(sizes...));
    }
}

template <class T, class U> void fill_all(std::vector<T> &v, const U &x) {
    if constexpr (is_vector<T>::value) {
        for (auto &u : v) fill_all(u, x);
    } else {
        std::fill(v.begin(), v.end(), T(x));
    }
}

template <class T, class U> int iota_all(std::vector<T> &v, U x, int offset = 0) {
    if constexpr (is_vector<T>::value) {
        for (auto &u : v) offset += iota_all(u, x + offset);
    } else {
        for (auto &u : v) u = x++, ++offset;
    }
    return offset;
}

template <class C> int mysize(const C &c) { return size(c); }


// T: commutative monoid, F: (U, T) -> U
template <class U, class T, class F>
U all_monoid_prod(const std::vector<T> &v, U unit, const F &f) {
    U res = unit;
    if constexpr (is_vector<T>::value) {
        for (const auto &x : v) res = f(res, all_monoid_prod(x, unit, f));
    } else {
        for (const auto &x : v) res = f(res, x);
    }
    return res;
}

template <class U, class T> U all_sum(const std::vector<T> &v, U unit = U()) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a + b; });
}
template <class U, class T> U all_prod(const std::vector<T> &v, U unit = U(1)) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a * b; });
}
template <class U, class T> U all_xor(const std::vector<T> &v, U unit = U()) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a ^ b; });
}
template <class U, class T> U all_and(const std::vector<T> &v, U unit = U(-1)) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a & b; });
}
template <class U, class T> U all_or(const std::vector<T> &v, U unit = U()) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a | b; });
}
template <class U, class T> U all_min(const std::vector<T> &v) {
    return all_monoid_prod<monoid::Min<U>, T>(v, monoid::Min<U>::unit(), monoid::Min<U>::op);
}
template <class U, class T> U all_max(const std::vector<T> &v) {
    return all_monoid_prod<monoid::Max<U>, T>(v, monoid::Max<U>::unit(), monoid::Max<U>::op);
}
template <class U, class T> U all_gcd(const std::vector<T> &v, U unit = U()) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return std::gcd(a, b); });
}
template <class U, class T> U all_lcm(const std::vector<T> &v, U unit = U(1)) {
    return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return std::lcm(a, b); });
}

} // namespace kk2

#endif // KK2_TEMPLATE_FUNCTION_UTIL_HPP
#ifndef KK2_TEMPLATE_IO_UTIL_HPP
#define KK2_TEMPLATE_IO_UTIL_HPP 1



// なんかoj verifyはプロトタイプ宣言が落ちる

namespace impl {

struct read {
    template <class IStream, class T> inline static void all_read(IStream &is, T &x) { is >> x; }

    template <class IStream, class T, class U>
    inline static void all_read(IStream &is, std::pair<T, U> &p) {
        all_read(is, p.first);
        all_read(is, p.second);
    }

    template <class IStream, class T> inline static void all_read(IStream &is, std::vector<T> &v) {
        for (T &x : v) all_read(is, x);
    }

    template <class IStream, class T, size_t F>
    inline static void all_read(IStream &is, std::array<T, F> &a) {
        for (T &x : a) all_read(is, x);
    }
};

struct write {
    template <class OStream, class T> inline static void all_write(OStream &os, const T &x) {
        os << x;
    }

    template <class OStream, class T, class U>
    inline static void all_write(OStream &os, const std::pair<T, U> &p) {
        all_write(os, p.first);
        all_write(os, ' ');
        all_write(os, p.second);
    }

    template <class OStream, class T>
    inline static void all_write(OStream &os, const std::vector<T> &v) {
        for (int i = 0; i < (int)v.size(); ++i) {
            if (i) all_write(os, ' ');
            all_write(os, v[i]);
        }
    }

    template <class OStream, class T, size_t F>
    inline static void all_write(OStream &os, const std::array<T, F> &a) {
        for (int i = 0; i < (int)F; ++i) {
            if (i) all_write(os, ' ');
            all_write(os, a[i]);
        }
    }
};

} // namespace impl

template <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::pair<T, U> &p) {
    impl::read::all_read(is, p);
    return is;
}

template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::vector<T> &v) {
    impl::read::all_read(is, v);
    return is;
}

template <class IStream, class T, size_t F, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::array<T, F> &a) {
    impl::read::all_read(is, a);
    return is;
}

template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::pair<T, U> &p) {
    impl::write::all_write(os, p);
    return os;
}

template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::vector<T> &v) {
    impl::write::all_write(os, v);
    return os;
}

template <class OStream, class T, size_t F, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::array<T, F> &a) {
    impl::write::all_write(os, a);
    return os;
}

#endif // KK2_TEMPLATE_IO_UTIL_HPP
#ifndef KK2_TEMPLATE_MACROS_HPP
#define KK2_TEMPLATE_MACROS_HPP 1

#define rep1(a) for (long long _ = 0; _ < (long long)(a); ++_)
#define rep2(i, a) for (long long i = 0; i < (long long)(a); ++i)
#define rep3(i, a, b) for (long long i = (a); i < (long long)(b); ++i)
#define repi2(i, a) for (long long i = (a) - 1; i >= 0; --i)
#define repi3(i, a, b) for (long long i = (a) - 1; i >= (long long)(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) begin(p), end(p)

#endif // KK2_TEMPLATE_MACROS_HPP

struct FastIOSetUp {
    FastIOSetUp() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} fast_io_set_up;

auto &kin = std::cin;
auto &kout = std::cout;
auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>;

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"); }
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); }

std::istream &operator>>(std::istream &is, u128 &x) {
    std::string s;
    is >> s;
    x = 0;
    for (char c : s) {
        assert('0' <= c && c <= '9');
        x = x * 10 + c - '0';
    }
    return is;
}

std::istream &operator>>(std::istream &is, i128 &x) {
    std::string s;
    is >> s;
    bool neg = s[0] == '-';
    x = 0;
    for (int i = neg; i < (int)s.size(); i++) {
        assert('0' <= s[i] && s[i] <= '9');
        x = x * 10 + s[i] - '0';
    }
    if (neg) x = -x;
    return is;
}

std::ostream &operator<<(std::ostream &os, u128 x) {
    if (x == 0) return os << '0';
    std::string s;
    while (x) {
        s.push_back('0' + x % 10);
        x /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}

std::ostream &operator<<(std::ostream &os, i128 x) {
    if (x == 0) return os << '0';
    if (x < 0) {
        os << '-';
        x = -x;
    }
    std::string s;
    while (x) {
        s.push_back('0' + x % 10);
        x /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}

#endif // KK2_TEMPLATE_PROCON_HPP
#ifndef KK2_TEMPLATE_DEBUG_HPP
#define KK2_TEMPLATE_DEBUG_HPP 1


#ifndef KK2_TYPE_TRAITS_MEMBER_HPP
#define KK2_TYPE_TRAITS_MEMBER_HPP 1



namespace kk2 {

#define HAS_MEMBER_FUNC(member)                                                                    \
    template <typename T, typename... Ts> struct has_member_func_##member##_impl {                 \
        template <typename U>                                                                      \
        static std::true_type check(decltype(std::declval<U>().member(std::declval<Ts>()...)) *);  \
        template <typename U> static std::false_type check(...);                                   \
        using type = decltype(check<T>(nullptr));                                                  \
    };                                                                                             \
    template <typename T, typename... Ts> struct has_member_func_##member                          \
        : has_member_func_##member##_impl<T, Ts...>::type {};                                      \
    template <typename T, typename... Ts> using has_member_func_##member##_t =                     \
        std::enable_if_t<has_member_func_##member<T, Ts...>::value>;                               \
    template <typename T, typename... Ts> using not_has_member_func_##member##_t =                 \
        std::enable_if_t<!has_member_func_##member<T, Ts...>::value>;

#define HAS_MEMBER_VAR(member)                                                                     \
    template <typename T> struct has_member_var_##member##_impl {                                  \
        template <typename U> static std::true_type check(decltype(std::declval<U>().member) *);   \
        template <typename U> static std::false_type check(...);                                   \
        using type = decltype(check<T>(nullptr));                                                  \
    };                                                                                             \
    template <typename T> struct has_member_var_##member                                           \
        : has_member_var_##member##_impl<T>::type {};                                              \
    template <typename T> using has_member_var_##member##_t =                                      \
        std::enable_if_t<has_member_var_##member<T>::value>;                                       \
    template <typename T> using not_has_member_var_##member##_t =                                  \
        std::enable_if_t<!has_member_var_##member<T>::value>;

HAS_MEMBER_FUNC(debug_output)
HAS_MEMBER_FUNC(val)


#undef HAS_MEMBER_FUNC
#undef HAS_MEMBER_VAR
} // namespace kk2

#endif // KK2_TYPE_TRAITS_MEMBER_HPP

namespace kk2 {

namespace debug {

#ifdef KK2

template <class OStream, is_ostream_t<OStream> *> void output(OStream &os);
template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const T &t);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::vector<T> &v);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::vector<std::vector<T>> &d);
template <class OStream, class T, size_t F, is_ostream_t<OStream> *>
void output(OStream &os, const std::array<T, F> &a);
template <class OStream, class T, class U, is_ostream_t<OStream> *>
void output(OStream &os, const std::pair<T, U> &p);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::queue<T> &q);
template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> *>
void output(OStream &os, const std::priority_queue<T, Container, Compare> &q);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::deque<T> &d);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::stack<T> &s);
template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *>
void output(OStream &os, const std::set<Key, Compare, Allocator> &s);
template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *>
void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s);
template <class OStream,
          class Key,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s);
template <class OStream,
          class Key,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s);
template <class OStream,
          class Key,
          class T,
          class Compare,
          class Allocator,
          is_ostream_t<OStream> *>
void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m);
template <class OStream,
          class Key,
          class T,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m);
template <class OStream, is_ostream_t<OStream> * = nullptr> void output(OStream &) {}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const T &t) {
    if constexpr (has_member_func_debug_output<T, OStream &>::value) {
        t.debug_output(os);
    } else {
        os << t;
    }
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::vector<T> &v) {
    os << "[";
    for (int i = 0; i < (int)v.size(); i++) {
        output(os, v[i]);
        if (i + 1 != (int)v.size()) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::vector<std::vector<T>> &d) {
    os << "[\n";
    for (int i = 0; i < (int)d.size(); i++) {
        output(os, d[i]);
        output(os, "\n");
    }
    os << "]";
}

template <class OStream, class T, size_t F, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::array<T, F> &a) {
    os << "[";
    for (int i = 0; i < (int)F; i++) {
        output(os, a[i]);
        if (i + 1 != (int)F) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, class U, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::pair<T, U> &p) {
    os << "(";
    output(os, p.first);
    os << ", ";
    output(os, p.second);
    os << ")";
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::queue<T> &q) {
    os << "[";
    std::queue<T> tmp = q;
    while (!tmp.empty()) {
        output(os, tmp.front());
        tmp.pop();
        if (!tmp.empty()) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::priority_queue<T, Container, Compare> &q) {
    os << "[";
    std::priority_queue<T, Container, Compare> tmp = q;
    while (!tmp.empty()) {
        output(os, tmp.top());
        tmp.pop();
        if (!tmp.empty()) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::deque<T> &d) {
    os << "[";
    std::deque<T> tmp = d;
    while (!tmp.empty()) {
        output(os, tmp.front());
        tmp.pop_front();
        if (!tmp.empty()) os << ", ";
    }
    os << "]";
}

template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::stack<T> &s) {
    os << "[";
    std::stack<T> tmp = s;
    std::vector<T> v;
    while (!tmp.empty()) {
        v.push_back(tmp.top());
        tmp.pop();
    }
    for (int i = (int)v.size() - 1; i >= 0; i--) {
        output(os, v[i]);
        if (i != 0) os << ", ";
    }
    os << "]";
}

template <class OStream,
          class Key,
          class Compare,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::set<Key, Compare, Allocator> &s) {
    os << "{";
    std::set<Key, Compare, Allocator> tmp = s;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, *it);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class Compare,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s) {
    os << "{";
    std::multiset<Key, Compare, Allocator> tmp = s;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, *it);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s) {
    os << "{";
    std::unordered_set<Key, Hash, KeyEqual, Allocator> tmp = s;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, *it);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s) {
    os << "{";
    std::unordered_multiset<Key, Hash, KeyEqual, Allocator> tmp = s;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, *it);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class T,
          class Compare,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m) {
    os << "{";
    std::map<Key, T, Compare, Allocator> tmp = m;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, it->first);
        os << ": ";
        output(os, it->second);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream,
          class Key,
          class T,
          class Hash,
          class KeyEqual,
          class Allocator,
          is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m) {
    os << "{";
    std::unordered_map<Key, T, Hash, KeyEqual, Allocator> tmp = m;
    for (auto it = tmp.begin(); it != tmp.end(); ++it) {
        output(os, it->first);
        os << ": ";
        output(os, it->second);
        if (std::next(it) != tmp.end()) os << ", ";
    }
    os << "}";
}

template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const T &t, const Args &...args) {
    output(os, t);
    os << ' ';
    output(os, args...);
}

template <class OStream, is_ostream_t<OStream> * = nullptr> void outputln(OStream &os) {
    os << '\n';
    os.flush();
}

template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr>
void outputln(OStream &os, const T &t, const Args &...args) {
    output(os, t, args...);
    os << '\n';
    os.flush();
}

std::vector<std::string> sep(const char *s) {
    std::vector<std::string> res;
    std::string now;
    int dep = 0;
    while (true) {
        if (*s == '\0') {
            res.emplace_back(now);
            break;
        }
        if (*s == '(' or *s == '[' or *s == '{') dep++;
        if (*s == ')' or *s == ']' or *s == '}') dep--;
        if (dep == 0 and *s == ',') {
            res.emplace_back(now);
            now.clear();
        } else if (!isspace(*s)) {
            now += *s;
        }
        s++;
    }
    return res;
}

void show_vars(const std::vector<std::string> &, int) {}

template <class T, class... Args>
void show_vars(const std::vector<std::string> &name, int pos, const T &t, const Args &...args) {
    assert(pos < (int)name.size());
    output(std::cerr, name[pos++] + ":", t);
    if (sizeof...(args) > 0) output(std::cerr, ", ");
    show_vars(name, pos, args...);
}

#define kdebug(...)                                                                                \
    kk2::debug::output(std::cerr, "line:" + std::to_string(__LINE__));                             \
    kk2::debug::output(std::cerr, ' ');                                                            \
    kk2::debug::show_vars(kk2::debug::sep(#__VA_ARGS__), 0, __VA_ARGS__);                          \
    kk2::debug::outputln(std::cerr);

#else

template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr>
void output(OStream &, const Args &...) {}

template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr>
void outputln(OStream &, const Args &...) {}

template <class... Args> void fix_warn(const Args &...) {}

#define kdebug(...) kk2::debug::fix_warn(__VA_ARGS__);

#endif // KK2

} // namespace debug

} // namespace kk2

#endif // KK2_TEMPLATE_DEBUG_HPP
#ifndef KK2_SEGMENT_TREE_SEG_HPP
#define KK2_SEGMENT_TREE_SEG_HPP 1


namespace kk2 {

template <class S, S (*op)(S, S), S (*e)()> struct SegmentTree {
  public:
    SegmentTree() : SegmentTree(0) {}

    SegmentTree(int n) : _n(n) {
        log = 0;
        while ((1U << log) < (unsigned int)(_n)) log++;
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
    }

    template <class... Args> SegmentTree(int n, Args... args)
        : SegmentTree(std::vector<S>(n, S(args...))){};

    SegmentTree(const std::vector<S> &v) : _n(int(v.size())) {
        log = 0;
        while ((1U << log) < (unsigned int)(_n)) log++;
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        build();
    }

    void build() {
        assert(!is_built);
        is_built = true;
        for (int i = size - 1; i >= 1; i--) { update(i); }
    }

    template <class... Args> void init_set(int p, Args... args) {
        assert(0 <= p && p < _n);
        assert(!is_built);
        d[p + size] = S(args...);
    }

    using Monoid = S;

    static S Op(S l, S r) { return op(l, r); }

    static S MonoidUnit() { return e(); }

    template <class... Args> void set(int p, Args... args) {
        assert(0 <= p && p < _n);
        assert(is_built);
        p += size;
        d[p] = S(args...);
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        assert(is_built);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        assert(is_built);
        S sml = e(), smr = e();
        l += size;
        r += size;

        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() {
        assert(is_built);
        return d[1];
    }

    // return r s.t.
    // r = l or f(op(a[l], a[l+1], ..., a[r-1])) == true
    // r = n or f(op(a[l], a[l+1], ..., a[r]))   == false
    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }

    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        assert(is_built);
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(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;
    }

    // return l s.t.
    // l = r or f(op(a[l], a[l], ..., a[r-1]))   == true
    // l = 0 or f(op(a[l-1], a[l], ..., a[r-1])) == false
    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }

    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        assert(is_built);
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(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;
    bool is_built = false;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

template <class M> using SegmentTreeS = SegmentTree<M, M::op, M::unit>;

} // namespace kk2

#endif // KK2_SEGMENT_TREE_SEG_HPP
#ifndef KK2_SEGMENT_TREE_LAZY_HPP
#define KK2_SEGMENT_TREE_LAZY_HPP 1


namespace kk2 {

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct LazySegmentTree {
  public:
    LazySegmentTree() : LazySegmentTree(0) {}

    LazySegmentTree(int n) : _n(n) {
        log = 0;
        while ((1ll << log) < _n) log++;
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
    }

    template <class... Args> LazySegmentTree(int n, Args... args)
        : LazySegmentTree(std::vector<S>(n, S(args...))) {}

    LazySegmentTree(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];
        build();
    }

    void build() {
        assert(!is_built);
        is_built = true;
        for (int i = size - 1; i >= 1; i--) { update(i); }
    }

    template <class... Args> void init_set(int p, Args... args) {
        assert(0 <= p && p < _n);
        assert(!is_built);
        d[p + size] = S(args...);
    }

    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(); }

    template <class... Args> void set(int p, Args... args) {
        assert(0 <= p && p < _n);
        assert(is_built);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = S(args...);
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        assert(is_built);
        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);
        assert(is_built);
        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() {
        assert(is_built);
        return d[1];
    }

    template <class... Args> void apply_point(int p, Args... args) {
        assert(0 <= p && p < _n);
        assert(is_built);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(F(args...), d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    template <class... Args> void apply_range(int l, int r, Args... args) {
        assert(0 <= l && l <= r && r <= _n);
        assert(is_built);
        if (l == r) return;
        F f = F(args...);

        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 <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()));
        assert(is_built);
        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()));
        assert(is_built);
        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;
    bool is_built = false;

    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();
    }
};

template <class A> using LazySegmentTreeS = LazySegmentTree<typename A::S,
                                                            A::S::op,
                                                            A::S::unit,
                                                            typename A::A,
                                                            A::act,
                                                            A::A::op,
                                                            A::A::unit>;

} // namespace kk2

#endif // KK2_SEGMENT_TREE_LAZY_HPP
#ifndef KK2_MATH_ACTION_ADD_MAX_HPP
#define KK2_MATH_ACTION_ADD_MAX_HPP 1

#ifndef KK2_MATH_GROUP_ADD_HPP
#define KK2_MATH_GROUP_ADD_HPP 1


namespace kk2 {

namespace group {

template <class S> struct Add {
    static constexpr bool commutative = true;
    using M = Add;
    S a;

    Add() : a(S()) {}
    Add(S a_) : a(a_) {}
    operator S() const { return a; }
    inline static M op(M l, M r) { return M(l.a + r.a); }
    inline static M inv(M x) { return M(-x.a); }
    inline static M unit() { return M(); }
    bool operator==(const M &rhs) const { return a == rhs.a; }
    bool operator!=(const M &rhs) const { return a != rhs.a; }

    template <class OStream, is_ostream_t<OStream> * = nullptr>
    friend OStream &operator<<(OStream &os, const M &x) {
        return os << x.a;
    }

    template <class IStream, is_istream_t<IStream> * = nullptr>
    friend IStream &operator>>(IStream &is, M &x) {
        return is >> x.a;
    }
};

} // namespace group

} // namespace kk2

#endif // KK2_MATH_GROUP_ADD_HPP

namespace kk2 {

namespace action {

template <class T, class Compare = std::less<T>> struct AddMax {
    using A = group::Add<T>;
    using S = monoid::Max<T, Compare>;

    inline static S act(A f, S x) { return x.is_unit ? x : S(x.a + f.a); }
};

} // namespace action

} // namespace kk2

#endif // KK2_MATH_ACTION_ADD_MAX_HPP
using namespace std;

void solve() {
    // 区切って，正の最大，負の最大を求めよう
    // 右端を固定したときの極値を列挙する
    using maxseg = kk2::SegmentTreeS<kk2::monoid::Max<int>>;
    using addmax = kk2::LazySegmentTreeS<kk2::action::AddMax<int>>;

    int n;
    kin >> n;
    vc<int> a(n);
    kin >> a;
    if (n == 2) {
        kout << i64(a[0]) * a[1] << "\n";
        return;
    }

    maxseg forward_plus(n), forward_minus(n);
    {
        addmax seg1(n), seg2(n);
        seg1.build(), seg2.build();
        rep (i, n) {
            seg1.apply_range(0, i, a[i]);
            seg2.apply_range(0, i, -a[i]);
            int next1 = max(a[i], seg1.prod(0, i).a);
            seg1.set(i, next1);
            forward_plus.init_set(i, next1);
            int next2 = max(-a[i], seg2.prod(0, i).a);
            seg2.set(i, next2);
            forward_minus.init_set(i, next2);
        }

        forward_plus.build(), forward_minus.build();
    }
    maxseg backward_plus(n), backward_minus(n);
    {
        addmax seg1(n), seg2(n);
        seg1.build(), seg2.build();
        repi (i, n) {
            seg1.apply_range(i, n, a[i]);
            seg2.apply_range(i, n, -a[i]);
            int next1 = max(a[i], seg1.prod(i, n).a);
            seg1.set(i, next1);
            backward_plus.init_set(i, next1);
            int next2 = max(-a[i], seg2.prod(i, n).a);
            seg2.set(i, next2);
            backward_minus.init_set(i, next2);
        }
        backward_plus.build(), backward_minus.build();
    }
    i64 res = -infty<i64>;
    rep (i, n) {
        chmax(res, i64(forward_plus.prod(0, i).a) * backward_plus.prod(i, n).a);
        chmax(res, i64(forward_minus.prod(0, i).a) * backward_minus.prod(i, n).a);
    }
    kout << res << kendl;
}

int main() {
    int t = 1;
    // kin >> t;
    rep (t) solve();

    return 0;
}
// Author: kk2
// converted by https://github.com/kk2a/cpp-bundle
// 2025-04-25 22:07:25
yukicoder

結果

ソースコード
