結果
| 問題 | No.2648 [Cherry 6th Tune D] 一次元の馬 |
| コンテスト | |
| ユーザー |
👑  希丝缇娜菲贝尔
|
| 提出日時 | 2026-11-09 12:55:35 |
| 言語 | C++23(gnu拡張gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 37,652 bytes |
| 記録 | |
| コンパイル時間 | 2,537 ms |
| コンパイル使用メモリ | 293,204 KB |
| 実行使用メモリ | 164,972 KB |
| 最終ジャッジ日時 | 2026-11-09 12:55:59 |
| 合計ジャッジ時間 | 19,785 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 WA * 34 |
ソースコード
// ---- begin std.cpp ----
// ---- begin templa/base.hpp ----
#ifndef CP_TEMPLA_BASE_HPP
#define CP_TEMPLA_BASE_HPP
#include <algorithm>
#include <array>
#include <bitset>
#include <bit>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#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>
// ---- begin templa/vec.hpp ----
#include <algorithm>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>
template<class Elem> struct vec;
/**
* @brief A mutable iterator range with common sequence algorithms.
* 中文：可变迭代器区间，提供常见序列操作。
* @details Obtain a view with v(), v(l,r), or v(i); indices and ranges are zero-based and half-open.
* 中文：使用 v()、v(l,r) 或 v(i) 获取视图；下标从 0 开始，区间为左闭右开。
*/
template<class Iter>
struct seq_view {
using Ref = typename std::iterator_traits<Iter>::reference;
using Elem = typename std::iterator_traits<Iter>::value_type;
Iter a, b;
Iter begin() const { return a; }
Iter end() const { return b; }
int size() const { return static_cast<int>(b - a); }
seq_view(Iter first, Iter last) : a(first), b(last) {}
seq_view sort() const {
std::sort(a, b);
return *this;
}
template<class Compare>
seq_view sort(Compare compare) const {
std::sort(a, b, compare);
return *this;
}
decltype(auto) operator[](int index) const { return *(a + index); }
template<class Compare = std::less<Elem>, class Result = vec<int>>
Result sorti(Compare compare = Compare{}) const {
Result order(size());
for (int i = 0; i < size(); ++i) order[i] = i;
order().sort([&](int lhs, int rhs) { return compare(a[lhs], a[rhs]); });
return order;
}
template<class Result = vec<Elem>>
Result col() const {
return Result(begin(), end());
}
template<class Equal = std::equal_to<Elem>, class Result = vec<std::pair<Elem, int>>>
Result rle(Equal equal = Equal{}) const {
Result result;
for (const auto& value : *this) {
if (result.empty() || !equal(result.back().first, value)) result.emp(value, 1);
else ++result.back().second;
}
return result;
}
Iter uni() const { return std::unique(a, b); }
Iter lb(const Elem& value) const { return std::lower_bound(a, b, value); }
Iter ub(const Elem& value) const { return std::upper_bound(a, b, value); }
int lbi(const Elem& value) const { return static_cast<int>(lb(value) - a); }
int ubi(const Elem& value) const { return static_cast<int>(ub(value) - a); }
seq_view bound(const Elem& left, const Elem& right) const { return {lb(left), lb(right)}; }
template<class Compare>
Iter lb(const Elem& value, Compare compare) const {
return std::lower_bound(a, b, value, compare);
}
template<class Compare>
Iter ub(const Elem& value, Compare compare) const {
return std::upper_bound(a, b, value, compare);
}
template<class Predicate>
Iter when_true_to_false(Predicate predicate) const {
if (a == b) return a;
return std::lower_bound(a, b, *a,
[&](const Elem& value, const Elem&) { return predicate(value); });
}
seq_view same(const Elem& value) const { return {lb(value), ub(value)}; }
template<class Function>
auto map(Function function) const {
using ResultElem = std::decay_t<std::invoke_result_t<Function, Ref>>;
vec<ResultElem> result;
for (const auto& value : *this) result.emp(function(value));
return result;
}
Iter max() const { return std::max_element(a, b); }
Iter min() const { return std::min_element(a, b); }
template<class Compare>
Iter min(Compare compare) const { return std::min_element(a, b, compare); }
seq_view rev() const {
std::reverse(a, b);
return *this;
}
};
/**
* @brief Vector wrapper with chainable insertion and iterator-range helpers.
* 中文：支持链式插入和迭代器区间操作的 vector 封装。
* @details v() returns a mutable view; v(l,r) selects [l,r), and v(i) returns the iterator at index i.
* 中文：v() 返回可变视图；v(l,r) 选取 [l,r)；v(i) 返回下标 i 对应的迭代器。
*/
template<class Elem>
struct vec {
using Base = std::vector<Elem>;
using size_type = typename Base::size_type;
using Iter = typename Base::iterator;
using CIter = typename Base::const_iterator;
using Reference = typename Base::reference;
using ConstReference = typename Base::const_reference;
using View = seq_view<Iter>;
using CView = seq_view<CIter>;
vec() = default;
explicit vec(int count, const Elem& value = Elem())
: a(count > 0 ? static_cast<size_type>(count) : 0, value) {}
template<class InputIter>
vec(InputIter first, InputIter last) : a(first, last) {}
vec(std::initializer_list<Elem> values) : a(std::move(values)) {}
vec(Base values) : a(std::move(values)) {}
operator Base() const { return a; }
Iter begin() { return a.begin(); }
CIter begin() const { return a.begin(); }
CIter cbegin() const { return a.cbegin(); }
Iter end() { return a.end(); }
CIter end() const { return a.end(); }
CIter cend() const { return a.cend(); }
int size() const { return static_cast<int>(a.size()); }
bool empty() const { return a.empty(); }
Reference back() { return a.back(); }
ConstReference back() const { return a.back(); }
vec sortunied() const {
vec result = *this;
result().sort();
result.a.erase(result().uni(), result.end());
return result;
}
Iter operator()(int index) { return a.begin() + index; }
CIter operator()(int index) const { return a.begin() + index; }
View operator()(int left, int right) { return {(*this)(left), (*this)(right)}; }
CView operator()(int left, int right) const { return {(*this)(left), (*this)(right)}; }
View operator()() { return (*this)(0, size()); }
CView operator()() const { return (*this)(0, size()); }
Reference operator[](int index) { return a[index]; }
ConstReference operator[](int index) const { return a[index]; }
Base& operator*() { return a; }
const Base& operator*() const { return a; }
void reserve(size_type count) { a.reserve(count); }
void resize(size_type count) { a.resize(count); }
void resize(size_type count, const Elem& value) { a.resize(count, value); }
void clear() { a.clear(); }
void assign(size_type count, const Elem& value) { a.assign(count, value); }
template<class InputIter>
void assign(InputIter first, InputIter last) { a.assign(first, last); }
Iter erase(Iter position) { return a.erase(position); }
Iter erase(Iter first, Iter last) { return a.erase(first, last); }
vec& push(Elem value) {
a.push_back(std::move(value));
return *this;
}
template<class... Args>
vec& emp(Args&&... args) {
a.emplace_back(std::forward<Args>(args)...);
return *this;
}
template<class Range>
vec& app(const Range& values) {
for (const auto& value : values) a.push_back(value);
return *this;
}
Elem pop() {
Elem value = std::move(a.back());
a.pop_back();
return value;
}
bool operator==(const vec& other) const { return a == other.a; }
bool operator!=(const vec& other) const { return a != other.a; }
bool operator<(const vec& other) const { return a < other.a; }
bool operator<=(const vec& other) const { return a <= other.a; }
bool operator>(const vec& other) const { return a > other.a; }
bool operator>=(const vec& other) const { return a >= other.a; }
vec<vec<Elem>> pile(int count) const { return vec<vec<Elem>>(count, *this); }
template<class Predicate>
vec& filter(Predicate predicate) {
size_type write = 0;
for (size_type read = 0; read < a.size(); ++read) {
if (predicate(a[read])) std::swap(a[write++], a[read]);
}
a.resize(write);
return *this;
}
private:
Base a;
};
template<class Stream, class A, class B>
Stream& operator>>(Stream& input, vec<std::pair<A, B>>& values) {
for (auto& value : values) input >> value.first >> value.second;
return input;
}
template<class Stream, class T>
Stream& operator>>(Stream& input, vec<T>& values) {
for (auto& value : values) input >> value;
return input;
}
template<class Stream, class T>
Stream& operator<<(Stream& output, const vec<T>& values) {
for (int i = 0; i < values.size(); ++i) {
if (i) output << ' ';
output << values[i];
}
return output;
}
template<class Stream, class A, class B>
Stream& operator<<(Stream& output, const vec<std::pair<A, B>>& values) {
for (int i = 0; i < values.size(); ++i) {
if (i) output << ' ';
output << '(' << values[i].first << ',' << values[i].second << ')';
}
return output;
}
// ---- end templa/vec.hpp ----
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128_t;
using u128 = __uint128_t;
constexpr int inf = 1 << 30;
constexpr ll INF = 1LL << 60;
constexpr ll LINF = 0x1fffffffffffffffLL;
constexpr ll MINF = 0x7fffffffffffLL;
constexpr int MOD = 1'000'000'007;
constexpr int MODD = 998'244'353;
template <class A, class B>
bool chmax(A& a, const B& b) { return b > a ? (a = b, true) : false; }
template <class A, class B>
bool chmin(A& a, const B& b) { return b < a ? (a = b, true) : false; }
#define sz(x) ((long long)(x).size())
// rep supports rep(n), rep(i,n), rep(i,l,r), and rep(i,l,r,step).
// 中文：rep 支持 rep(n)、rep(i,n)、rep(i,l,r) 和 rep(i,l,r,step) 四种循环形式。
#define CP_REP1(n) for (ll _ = 0; _ < (n); ++_)
#define CP_REP2(i, n) for (ll i = 0; i < (n); ++i)
#define CP_REP3(i, a, b) for (ll i = (a); i < (b); ++i)
#define CP_REP4(i, a, b, step) for (ll i = (a); i < (b); i += (step))
#define CP_REP_SELECT(_1, _2, _3, _4, NAME, ...) NAME
#define rep(...) CP_REP_SELECT(__VA_ARGS__, CP_REP4, CP_REP3, CP_REP2, CP_REP1)(__VA_ARGS__)
#define Rep(i, a, b) for (ll i = (a); i < (b); ++i)
// rrep supports rrep(n), rrep(i,n), and rrep(i,l,r), over half-open ranges.
// 中文：rrep 支持 rrep(n)、rrep(i,n) 和 rrep(i,l,r)，循环范围按左闭右开处理。
#define CP_RREP1(n) for (ll _ = (n); _-- > 0; )
#define CP_RREP2(i, n) for (ll i = (n); i-- > 0; )
#define CP_RREP3(i, a, b) for (ll i = (b); i-- > (a); )
#define CP_RREP_SELECT(_1, _2, _3, NAME, ...) NAME
#define rrep(...) CP_RREP_SELECT(__VA_ARGS__, CP_RREP3, CP_RREP2, CP_RREP1)(__VA_ARGS__)
// each(range) iterates values; each(key,value,range) destructures pairs.
// 中文：each(range) 遍历元素；each(key,value,range) 可解构遍历键值对。
#define CP_EACH1(i, range) for (auto&& i : range)
#define CP_EACH2(x, y, range) for (auto&& [x, y] : range)
#define CP_EACH3(x, y, z, range) for (auto&& [x, y, z] : range)
#define CP_EACH4(w, x, y, z, range) for (auto&& [w, x, y, z] : range)
#define CP_EACH_SELECT(_1, _2, _3, _4, _5, NAME, ...) NAME
#define each(...) CP_EACH_SELECT(__VA_ARGS__, CP_EACH4, CP_EACH3, CP_EACH2, CP_EACH1)(__VA_ARGS__)
#define CP_ALL1(c) begin(c), end(c)
#define CP_ALL2(c, n) begin(c), begin(c) + (n)
#define CP_ALL3(c, l, r) begin(c) + (l), begin(c) + (r)
#define CP_ALL_SELECT(_1, _2, _3, NAME, ...) NAME
#define all(...) CP_ALL_SELECT(__VA_ARGS__, CP_ALL3, CP_ALL2, CP_ALL1)(__VA_ARGS__)
#define CP_RALL1(c) rbegin(c), rend(c)
#define CP_RALL2(c, n) rbegin(c), rbegin(c) + (n)
#define CP_RALL3(c, l, r) rbegin(c) + (l), rbegin(c) + (r)
#define rall(...) CP_ALL_SELECT(__VA_ARGS__, CP_RALL3, CP_RALL2, CP_RALL1)(__VA_ARGS__)
#define sum(...) accumulate(all(__VA_ARGS__), 0LL)
#define dsum(...) accumulate(all(__VA_ARGS__), 0.0L)
#define Msum(...) accumulate(all(__VA_ARGS__), mint{})
#define elif else if
#define fst first
#define snd second
#define pb push_back
#define em emplace_back
#define is insert
#define el '\n'
template<class T> using V = vec<T>;
template<class T, size_t N> using AR = array<T, N>;
template<class T> using v = vector<T>;
template<class T, size_t N> using a = array<T, N>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
namespace cp_detail {
template<class T, class = void> struct is_iterable : false_type {};
template<class T> struct is_iterable<T, void_t<decltype(begin(declval<const T&>())),
decltype(end(declval<const T&>()))>> : true_type {};
template<class T, class = void> struct is_tuple_like : false_type {};
template<class T> struct is_tuple_like<T, void_t<decltype(tuple_size<decay_t<T>>::value)>> : true_type {};
template<class T> struct is_pair : false_type {};
template<class A, class B> struct is_pair<pair<A, B>> : true_type {};
template<class T, class = void> struct is_input_streamable : false_type {};
template<class T> struct is_input_streamable<T, void_t<decltype(declval<istream&>() >> declval<T&>())>> : true_type {};
template<class T, enable_if_t<!is_iterable<T>::value && !is_pair<T>::value && !is_tuple_like<T>::value, int> = 0>
void print_debug(const T& x) { cerr << x; }
inline void print_debug(const string& x) { cerr << '"' << x << '"'; }
inline void print_debug(const char* x) { cerr << '"' << x << '"'; }
inline void print_debug(char x) { cerr << '\'' << x << '\''; }
inline void print_debug(bool x) { cerr << (x ? "true" : "false"); }
template<class A, class B> void print_debug(const pair<A, B>& p) {
cerr << '('; print_debug(p.first); cerr << ", "; print_debug(p.second); cerr << ')';
}
template<class T, enable_if_t<is_tuple_like<T>::value && !is_pair<T>::value, int> = 0>
void print_debug(const T& value);
template<class T, enable_if_t<is_iterable<T>::value && !is_tuple_like<T>::value, int> = 0>
void print_debug(const T& xs) {
cerr << '['; bool first = true;
for (const auto& x : xs) { if (!first) cerr << ", "; first = false; print_debug(x); }
cerr << ']';
}
template<class T, size_t... I>
void print_debug_tuple(const T& value, index_sequence<I...>) {
cerr << '(';
bool first = true;
((first ? (first = false, void()) : (cerr << ", ", void()),
print_debug(get<I>(value))), ...);
cerr << ')';
}
template<class T, enable_if_t<is_tuple_like<T>::value && !is_pair<T>::value, int>>
void print_debug(const T& value) {
print_debug_tuple(value, make_index_sequence<tuple_size<decay_t<T>>::value>{});
}
/** @brief Recursively reads scalars, pairs, tuples, arrays, and nested containers.
* 中文：递归读取标量、pair、tuple、数组和嵌套容器。 */
template<class T> void read_one(T& value) {
using U = decay_t<T>;
if constexpr (is_same_v<U, string> || is_input_streamable<T>::value) {
cin >> value;
} else if constexpr (is_same_v<U, vector<bool>>) {
for (auto&& bit : value) { bool x; read_one(x); bit = x; }
} else if constexpr (is_pair<U>::value) {
read_one(value.first); read_one(value.second);
} else if constexpr (is_tuple_like<U>::value) {
apply([](auto&... xs) { (read_one(xs), ...); }, value);
} else if constexpr (is_iterable<U>::value) {
for (auto&& item : value) read_one(item);
} else {
static_assert(is_input_streamable<T>::value, "type cannot be read by rd/in");
}
}
/** @brief Recursively prints scalars, pairs, tuples, and containers separated by spaces.
* 中文：递归输出标量、pair、tuple 和容器，各元素以空格分隔。 */
template<class T> void write_one(const T& value);
template<class T, size_t... I>
void write_tuple(const T& value, index_sequence<I...>) {
bool first = true;
((first ? (first = false, void()) : (cout << ' ', void()),
write_one(get<I>(value))), ...);
}
template<class T> void write_one(const T& value) {
using U = decay_t<T>;
if constexpr (is_same_v<U, string>) {
cout << value;
} else if constexpr (is_tuple_like<U>::value) {
write_tuple(value, make_index_sequence<tuple_size<U>::value>{});
} else if constexpr (is_iterable<U>::value && !is_same_v<U, string>) {
bool first = true;
for (const auto& item : value) {
if (!first) cout << ' ';
first = false;
write_one(item);
}
} else {
cout << value;
}
}
template<class... Ts> void debug_values(const char* names, const Ts&... xs) {
cerr << "\033[33m[debug] " << names << " = ";
bool first = true;
((first ? (first = false, void()) : (cerr << " | ", void()), print_debug(xs)), ...);
cerr << "\033[0m\n";
}
}
#ifdef DEBUG
#define debug(...) do { cp_detail::debug_values(#__VA_ARGS__, __VA_ARGS__); } while (0)
#else
#define debug(...) ((void)0)
#endif
#define dbg(...) debug(__VA_ARGS__)
#define as(...) assert(__VA_ARGS__)
/// @brief Defines yes/no output helpers named after the two arguments.
/// 中文：定义以两个参数命名的 yes/no 输出函数。
#define YESNO(yes_name, no_name) \
inline void yes_name(bool value = true) { out(value ? #yes_name : #no_name); } \
inline void no_name() { out(#no_name); }
/** @brief Reads one or more values; vectors, arrays, pairs, and tuples recurse elementwise.
* 中文：读取一个或多个值；vector、数组、pair 和 tuple 会递归读取各元素。 */
template<class... Ts> void rd(Ts&... xs) { (cp_detail::read_one(xs), ...); }
/// @brief Alias for rd, matching the compact input style used by contest templates.
/// 中文：rd 的别名，采用竞赛模板常用的简短输入写法。
template<class... Ts> void in(Ts&... xs) { rd(xs...); }
template<class... Ts> void wt(const Ts&... xs) {
bool first = true;
((first ? (first = false, void()) : (cout << ' ', void()), cp_detail::write_one(xs)), ...);
cout << '\n';
}
/// @brief Alias for wt: prints values separated by spaces and appends a newline.
/// 中文：wt 的别名：各值以空格分隔，并在末尾换行。
template<class... Ts> void out(const Ts&... xs) { wt(xs...); }
YESNO(first, second)
YESNO(First, Second)
YESNO(Yes, No)
YESNO(YES, NO)
YESNO(possible, impossible)
YESNO(Possible, Impossible)
YESNO(POSSIBLE, IMPOSSIBLE)
// Declare scalar variables and read them in one statement.
// 中文：在一条语句中声明标量变量并读入。
#define INT(...) int __VA_ARGS__; rd(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; rd(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__; rd(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; rd(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; rd(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; rd(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; rd(__VA_ARGS__)
/// @brief Declares a vector initialized with constructor arguments; does not read input.
/// 中文：声明并按构造参数初始化 vector；不会读取输入。
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
/// @brief Declares a fixed-size array value-initialized to zero/default values.
/// 中文：声明固定长度数组，并用零值/默认值初始化。
#define arr(type, name, size) array<type, size> name{}
/// @brief Declares an n-element vector and reads every element from input.
/// 中文：声明含 n 个元素的 vector，并读取所有元素。
#define VEC(type, name, n) vec<type> name(n); rd(name)
/// @brief Declares a fixed-size array and recursively reads its elements.
/// 中文：声明固定长度数组，并递归读取其中元素。
#define ARR(type, name, n) array<type, n> name{}; rd(name)
/// @brief Declares a 2D vector initialized with the given fill value; does not read input.
/// 中文：声明并按给定填充值初始化二维 vector；不会读取输入。
#define vv(type, name, h, ...) vec<vec<type>> name(h, vec<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) vec<vec<vec<type>>> name(h, vec<vec<type>>(w, vec<type>(__VA_ARGS__)))
/// @brief Declares an h-by-w 2D vec and recursively reads every element.
/// 中文：声明 h×w 二维 vec，并递归读取所有元素。
#define VV(type, name, h, w) vec<vec<type>> name(h, vec<type>(w)); rd(name)
/// @brief Declares an h-by-w-by-d 3D vec and recursively reads every element.
/// 中文：声明 h×w×d 三维 vec，并递归读取所有元素。
#define VVV(type, name, h, w, d) vec<vec<vec<type>>> name(h, vec<vec<type>>(w, vec<type>(d))); rd(name)
constexpr ll debug_const(ll judge_value, ll debug_value) {
#ifdef DEBUG
return debug_value;
#else
return judge_value;
#endif
}
#endif // CP_TEMPLA_BASE_HPP
// ---- end templa/base.hpp ----
// ---- begin templa/common.hpp ----
/**
* @file common.hpp
* @brief Common precomputation and search helpers.
* 中文：常用预处理与搜索工具。
* @details Include with #include "templa/common.hpp". Names are placed in
* 中文：通过 #include "templa/common.hpp" 引入；函数放在
* namespace cp to avoid collisions with standard-library algorithms.
* 中文：cp 命名空间中，以避免与标准库算法重名。
*/
namespace cp {
/**
* @brief Finds the last/first boundary of a monotone predicate on integers.
* 中文：在整数范围内二分查找单调谓词的边界。
* @param check Predicate that is true at ok and false at ng.
* 中文：谓词 check 在 ok 处为真，在 ng 处为假。
* @param ok Known true endpoint; @param ng known false endpoint.
* 中文：ok 是已知为真的端点；ng 是已知为假的端点。
* @details Returns ok when endpoints are adjacent. The endpoint order may be
* 中文：当两端点相邻时返回 ok；端点顺序可以
* increasing or decreasing. Set check_ok=false to skip the debug assertion.
* 中文：递增或递减。设置 check_ok=false 可跳过调试断言。
*/
template<class Check>
ll binary_search(Check check, ll ok, ll ng, bool check_ok = true) {
if (check_ok) assert(check(ok) && !check(ng));
while ((i128)ok - ng > 1 || (i128)ng - ok > 1) {
ll mid = std::midpoint(ok, ng);
(check(mid) ? ok : ng) = mid;
}
return ok;
}
/**
* @brief Binary search on a monotone predicate over real numbers.
* 中文：在实数范围内对单调谓词执行二分搜索。
* @param check Predicate true at ok and false at ng.
* 中文：谓词 check 在 ok 处为真，在 ng 处为假。
* @param iterations Number of bisection steps; defaults to 100.
* 中文：二分迭代次数，默认 100 次。
*/
template<class Check>
double binary_search_real(Check check, double ok, double ng, int iterations = 100) {
assert(check(ok) && !check(ng));
while (iterations--) {
double mid = std::midpoint(ok, ng);
(check(mid) ? ok : ng) = mid;
}
return std::midpoint(ok, ng);
}
/**
* @brief Returns the insertion index from lower_bound on a sorted range.
* 中文：在已排序区间上执行 lower_bound，并返回插入位置的下标。
* @details LB(v, x) is equivalent to lower_bound(begin(v), end(v), x) - begin(v).
* 中文：LB(v, x) 等价于 lower_bound(begin(v), end(v), x) - begin(v)。
*/
template<class Range, class T, class Compare = less<>>
ll LB(const Range& values, const T& target, Compare compare = Compare{}) {
return lower_bound(begin(values), end(values), target, compare) - begin(values);
}
/**
* @brief Returns the insertion index from upper_bound on a sorted range.
* 中文：在已排序区间上执行 upper_bound，并返回插入位置的下标。
* @details UB(v, x) is equivalent to upper_bound(begin(v), end(v), x) - begin(v).
* 中文：UB(v, x) 等价于 upper_bound(begin(v), end(v), x) - begin(v)。
*/
template<class Range, class T, class Compare = less<>>
ll UB(const Range& values, const T& target, Compare compare = Compare{}) {
return upper_bound(begin(values), end(values), target, compare) - begin(values);
}
/**
* @brief Builds prefix sums from a range.
* 中文：根据一个区间构造前缀和。
* @param leading_zero If true, result has n+1 elements and result[0] is zero.
* 中文：为 true 时，结果长度为 n+1，且 result[0] 为零。
* If false, result[i] is the inclusive prefix through input[i].
* 中文：为 false 时，result[i] 是截至 input[i]（含该项）的前缀和。
*/
template<class Range>
auto cumsum(const Range& values, bool leading_zero = true) {
using T = decay_t<decltype(*begin(values))>;
vector<T> prefix;
if (leading_zero) prefix.emplace_back(T{});
for (const auto& value : values) {
prefix.push_back((prefix.empty() ? T{} : prefix.back()) + value);
}
return prefix;
}
/** @brief Sorts a vector and removes duplicate values.
* 中文：对 vector 排序并删除重复值。 */
template<class T, class Compare = less<>>
void sort_unique(vector<T>& values, Compare compare = Compare{}) {
sort(values.begin(), values.end(), compare);
values.erase(unique(values.begin(), values.end()), values.end());
}
/**
* @brief Run-length encodes consecutive equal values.
* 中文：对连续相同的值进行游程编码。
* @return Pairs of {value, run length}, preserving input order.
* 中文：返回 {值, 连续长度}，并保持原有顺序。
*/
template<class Range>
auto run_length_encode(const Range& values) {
using T = decay_t<decltype(*begin(values))>;
vector<pair<T, ll>> result;
for (const auto& value : values) {
if (result.empty() || result.back().first != value) result.emplace_back(value, 1);
else ++result.back().second;
}
return result;
}
/**
* @brief Coordinate-compresses values.
* 中文：对数值进行坐标压缩。
* @return {sorted unique values, rank for each input element}.
* 中文：返回 {排序去重后的值, 每个输入元素对应的排名}。
*/
template<class Range>
auto coordinate_compress(const Range& input) {
using T = decay_t<decltype(*begin(input))>;
vector<T> values(begin(input), end(input));
sort_unique(values);
vector<ll> rank;
rank.reserve(values.size());
for (const auto& x : input)
rank.push_back(lower_bound(values.begin(), values.end(), x) - values.begin());
return pair<vector<T>, vector<ll>>(move(values), move(rank));
}
/** @brief Counts values equal to target in a range.
* 中文：统计区间中等于 target 的元素个数。 */
template<class Range, class Value>
ll count_value(const Range& values, const Value& target) {
return count(begin(values), end(values), target);
}
/** @brief Counts elements satisfying predicate.
* 中文：统计满足 predicate 的元素个数。 */
template<class Range, class Predicate>
ll count_if_value(const Range& values, Predicate predicate) {
return count_if(begin(values), end(values), move(predicate));
}
/** @brief Erases all elements satisfying predicate from a sequence container.
* 中文：从序列容器中删除所有满足 predicate 的元素。 */
template<class Sequence, class Predicate>
void filter_inplace(Sequence& values, Predicate predicate) {
values.erase(remove_if(values.begin(), values.end(), move(predicate)), values.end());
}
/** @brief Creates [first, first+n) as a vector of long long values.
* 中文：创建内容为 [first, first+n) 的 long long 向量。 */
inline vector<ll> iota_vector(ll n, ll first = 0) {
vector<ll> values(n);
iota(values.begin(), values.end(), first);
return values;
}
/** @brief Removes and returns the first value of a deque. Requires nonempty input.
* 中文：移除并返回 deque 的首元素；容器必须非空。 */
template<class T>
T pop(deque<T>& values) {
T result = move(values.front());
values.pop_front();
return result;
}
/** @brief Removes and returns the top value of a priority queue. Requires nonempty input.
* 中文：移除并返回优先队列的队首元素；容器必须非空。 */
template<class T, class Container, class Compare>
T pop(priority_queue<T, Container, Compare>& values) {
T result = values.top();
values.pop();
return result;
}
/** @brief Removes and returns the last value of a vector. Requires nonempty input.
* 中文：移除并返回 vector 的末尾元素；容器必须非空。 */
template<class T>
T pop(vector<T>& values) {
T result = move(values.back());
values.pop_back();
return result;
}
/** @brief Removes and returns the top value of a stack. Requires nonempty input.
* 中文：移除并返回栈顶元素；容器必须非空。 */
template<class T>
T pop(stack<T>& values) {
T result = values.top();
values.pop();
return result;
}
/** @brief Returns floor(a/b), rounding toward negative infinity; requires b != 0.
* 中文：返回 floor(a/b)，即向负无穷方向取整；要求 b != 0。 */
template<class T>
T floor_div(T a, T b) {
T q = a / b, r = a % b;
if (r != 0 && ((a < 0) != (b < 0))) --q;
return q;
}
/** @brief Returns ceil(a/b), rounding toward positive infinity; requires b != 0.
* 中文：返回 ceil(a/b)，即向正无穷方向取整；要求 b != 0。 */
template<class T>
T ceil_div(T a, T b) {
T q = a / b, r = a % b;
if (r != 0 && ((a < 0) == (b < 0))) ++q;
return q;
}
/** @brief Computes a^exponent modulo mod; requires exponent >= 0 and mod > 0.
* 中文：计算 a^exponent mod mod；要求 exponent >= 0 且 mod > 0。 */
inline ll mod_pow(ll a, ll exponent, ll mod) {
assert(mod > 0 && exponent >= 0);
a %= mod;
if (a < 0) a += mod;
ll result = 1 % mod;
while (exponent > 0) {
if (exponent & 1) result = (i128)result * a % mod;
a = (i128)a * a % mod;
exponent >>= 1;
}
return result;
}
/** @brief Returns prime factors as {prime, exponent}; n must be positive.
* 中文：返回格式为 {质因数, 指数} 的分解结果；n 必须为正数。 */
inline vector<pair<ll, ll>> factorize(ll n) {
assert(n > 0);
vector<pair<ll, ll>> factors;
for (ll p = 2; p <= n / p; ++p) {
if (n % p != 0) continue;
ll exponent = 0;
do { n /= p; ++exponent; } while (n % p == 0);
factors.emplace_back(p, exponent);
}
if (n > 1) factors.emplace_back(n, 1);
return factors;
}
/** @brief Returns all positive divisors of n in increasing order; n must be positive.
* 中文：按升序返回 n 的所有正因数；n 必须为正数。 */
inline vector<ll> divisors(ll n) {
assert(n > 0);
vector<ll> result;
for (ll d = 1; d <= n / d; ++d) {
if (n % d != 0) continue;
result.push_back(d);
if (d != n / d) result.push_back(n / d);
}
sort(result.begin(), result.end());
return result;
}
/** @brief Returns a boolean sieve where result[x] indicates whether x is prime.
* 中文：返回布尔筛，result[x] 表示 x 是否为质数。 */
inline vector<bool> prime_sieve(int n) {
assert(n >= 0);
vector<bool> prime(n + 1, true);
if (n >= 0) prime[0] = false;
if (n >= 1) prime[1] = false;
for (ll p = 2; p <= n / p; ++p)
if (prime[p]) for (ll x = p * p; x <= n; x += p) prime[x] = false;
return prime;
}
} // namespace cp
// ---- end templa/common.hpp ----
// ---- begin templa/dynamic_modint.hpp ----
/**
* @brief Runtime-modulus modular integer type.
* 中文：运行期模数的模整数类型。
* @details Call dynamic_modint<id>::set_mod(mod) before constructing values; each id has an independent modulus.
* 中文：构造模整数前调用 dynamic_modint<id>::set_mod(mod)；每个 id 使用独立模数。
*/
template<int id> class dynamic_modint {
using mint = dynamic_modint;
struct barrett {
uint32_t _m;
uint64_t im;
barrett(uint32_t mod) : _m(mod), im(uint64_t(-1) / mod + 1) {}
operator uint32_t() const { return _m; }
uint32_t mul(uint32_t a, uint32_t b) const {
uint64_t z = a;
z *= b;
uint64_t x = uint64_t(__uint128_t(z) * im >> 64);
uint64_t y = x * _m;
return uint32_t(z - y + (z < y ? _m : 0));
}
};
static inline barrett m = 1;
uint32_t _v = 0;
static pair<int32_t, int32_t> inv_gcd(int32_t a, int32_t b) {
if (a == 0) return {b, 0};
int32_t s = b, t = a, m0 = 0, m1 = 1;
while (t) {
const int32_t u = s / t;
s -= t * u; m0 -= m1 * u;
swap(s, t); swap(m0, m1);
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
public:
static mint raw(uint32_t v) { mint a; a._v = v; return a; }
dynamic_modint() {}
template <class T>
dynamic_modint(T v) {
static_assert(is_integral_v<T>, "T is not integral type.");
if constexpr (is_signed_v<T>) {
int64_t x = int64_t(v % int64_t(m));
if (x < 0) x += m; _v = uint32_t(x);
}
else _v = uint32_t(v % m);
}
static uint32_t mod() { return m; }
/// @brief Sets the modulus shared by every value with this template id.
/// 中文：设置该模板 id 下所有数值共用的模数。
static void set_mod(int mod) {
assert(1 <= mod);
m = mod;
}
uint32_t val() const { return _v; }
mint& operator++() { return *this += 1; }
mint& operator--() { return *this -= 1; }
mint operator++(int) { mint res = *this; ++*this; return res; }
mint operator--(int) { mint res = *this; --*this; return res; }
mint& operator+=(mint rhs) {
if (_v >= m - rhs._v) _v -= m;
_v += rhs._v; return *this;
}
mint& operator-=(mint rhs) {
if (_v < rhs._v) _v += m;
_v -= rhs._v; return *this;
}
mint& operator*=(mint rhs) { return *this = *this * rhs; }
mint& operator/=(mint rhs) { return *this *= rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint{} - *this; }
/// @brief Returns this value raised to n; n must be nonnegative.
/// 中文：返回当前值的 n 次幂；n 必须非负。
mint pow(long long n) const {
assert(0 <= n);
if(n == 0) return 1;
mint x = *this, r = 1;
while (1) {
if (n & 1) r *= x; n >>= 1;
if (n == 0) return r;
x *= x;
}
}
/// @brief Returns the multiplicative inverse; the value must be nonzero.
/// 中文：返回乘法逆元；当前值必须非零。
mint inv() const {
auto eg = inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(mint lhs, mint rhs) { return lhs += rhs; }
friend mint operator-(mint lhs, mint rhs) { return lhs -= rhs; }
friend mint operator*(mint lhs, mint rhs) { return raw(m.mul(lhs._v, rhs._v)); }
friend mint operator/(mint lhs, mint rhs) { return lhs /= rhs; }
friend bool operator==(mint lhs, mint rhs) { return lhs._v == rhs._v; }
friend bool operator!=(mint lhs, mint rhs) { return lhs._v != rhs._v; }
};
using mint = dynamic_modint<-1>;
istream& operator>>(istream& in, mint& x) { long long a; in >> a; x = a; return in; }
ostream& operator<<(ostream& out, mint x) { return out << x.val(); }
mint operator""_M(unsigned long long x) { return x; }
constexpr uint32_t fact_mx = 2e7;
mint fac[fact_mx + 1], inv[fact_mx + 1];
/// @brief Precomputes factorial and inverse-factorial tables up to fact_mx.
/// 中文：预处理到 fact_mx 的阶乘和逆阶乘表。
void prepare_factorial() {
fac[0] = 1;
for(uint32_t i = 1; i <= fact_mx; i++) fac[i] = fac[i - 1] * mint::raw(i);
inv[fact_mx] = fac[fact_mx].inv();
for(uint32_t i = fact_mx; i; i--) inv[i - 1] = inv[i] * mint::raw(i);
}
mint inverse(long long n) { return inv[n] * fac[n - 1]; }
mint perm(long long n, long long r) {
if(n < r || r < 0) return 0;
if(n > fact_mx) [[unlikely]] {
mint ans = 1, x = n;
while(r--) ans *= x--;
return ans;
}
return fac[n] * inv[n - r];
}
/// @brief Returns n choose r, or zero when r is outside [0,n].
/// 中文：返回组合数 n 选 r；r 不在 [0,n] 时返回 0。
mint comb(long long n, long long r) {
if(n < r || r < 0) return 0;
r = min(r, n - r);
const mint ans = perm(n, r);
return ans * inv[r];
}
template<class... T> mint comb(long long n, T... rs) {
if(n < 0) return 0;
mint ans = fac[n];
long long rn = n;
for(long long r : {rs...}) {
if(r < 0) return 0;
ans *= inv[r];
rn -= r;
}
if(rn < 0) return 0;
return ans * inv[rn];
}
mint Mcomb(long long n, long long r){ return comb(n + r - 1, r); } // r balls into n boxes
// ---- end templa/dynamic_modint.hpp ----
typedef mint mm;
#define REP rep
#define RREP rrep
bool __multi__ = true;
namespace XK {
void INIT();
void solve() {
INT(N); VEC(ll, A, N);
auto ck = [&](ll x) -> bool {
V<ll> X;
rep(i, N) X.push(A[i] + i * x);
rep(i, N - 1) if(X[i] >= X[i + 1]) return false;
return true;
};
wt(cp::binary_search(ck, INF, -1, false));
}
}
void XK::INIT() {
mm::set_mod(MOD);
// prepare_factorial();
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
XK::INIT();
if (__multi__) cin >> t;
while (t--) XK::solve();
}
// ---- end std.cpp ----