// ---- 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);
  ll ans = 0;
  rep(i, N - 1) chmax(ans, A[i] - A[i + 1] + 1);
  wt(ans);
}
}

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