#include <vector>
using namespace std;

int Binary_Search(int target, vector<int> &arr) {
    int left = 0, right = static_cast<int>(arr.size()) - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 在非负下标区间中避免 left+right 溢出
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}

#include <vector>
#include <algorithm>
using namespace std;

int lower_bound(const vector<int> &arr, int target) {
    int left = 0, right = arr.size(); // 注意右边界是 n
    while (left < right) {
        int mid = left + (right - left) / 2; // 防止整数溢出
        if (arr[mid] >= target)
            right = mid; // 收紧右边界，继续在左半部分查找
        else
            left = mid + 1; // 收紧左边界，在右半部分查找
    }
    return left; // 返回第一个 >= target 的下标
}

#include <vector>
#include <algorithm>
using namespace std;

int upper_bound(const vector<int> &arr, int target) {
    int left = 0, right = arr.size();
    while (left < right) {
        int mid = left + (right - left) / 2; // 防止整数溢出
        if (arr[mid] > target)
            right = mid; // 收紧右边界，继续在左半部分查找
        else
            left = mid + 1; // 收紧左边界，在右半部分查找
    }
    return left; // 返回第一个 > target 的下标
}

#include <vector>
using namespace std;

int bin_search(const vector<int> &arr, int target) {
    int left = 0, right = static_cast<int>(arr.size()) - 1;
    int result = -1; // 记录前驱位置

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // 找到目标值，直接返回
        } else if (arr[mid] < target) {
            result = mid;   // 记录可能的前驱位置
            left = mid + 1; // 继续在右半部分查找目标值
        } else {
            right = mid - 1; // 在左半部分查找
        }
    }

    return result; // 返回前驱位置或-1
}

#include <vector>
#include <utility>
using namespace std;

pair<int, int> twoSumBinary(const vector<int> &arr, int target) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        long long need = 1LL * target - arr[i]; // 计算需要的互补值

        // 在 (i+1 ... n-1) 范围内二分查找 need
        int left = i + 1, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止整数溢出
            if (arr[mid] == need)
                return {i, mid}; // 找到匹配对
            else if (arr[mid] < need)
                left = mid + 1; // 在右半部分继续查找
            else
                right = mid - 1; // 在左半部分继续查找
        }
    }
    return {-1, -1}; // 无解
}

#include <algorithm>
#include <cmath>
#include <stdexcept>
using namespace std;

double sqrt_binary(double x) {
    if (x < 0 || !isfinite(x))
        throw invalid_argument("x 必须是有限非负数");
    if (x == 0)
        return 0;
    double left = 0, right = max(1.0, x);
    for (int i = 0; i < 1100; ++i) {
        double mid = left + (right - left) / 2;
        if (mid == left || mid == right)
            break;
        if (mid > x / mid)
            right = mid; // 避免 mid*mid 溢出
        else
            left = mid;
    }
    return left;
}

#include <functional>
#include <cmath>
#include <stdexcept>
using namespace std;

double solve_root_binary(double a, double b, function<double(double)> f) {
    if (!isfinite(a) || !isfinite(b) || a > b)
        throw invalid_argument("区间无效");
    // 先处理端点就是零点的情况，再检查夹逼条件。
    double fa = f(a), fb = f(b);
    if (!isfinite(fa) || !isfinite(fb))
        throw invalid_argument("函数值必须有限");
    if (fa == 0)
        return a;
    if (fb == 0)
        return b;
    if ((fa < 0) == (fb < 0))
        throw invalid_argument("端点须异号或已经为零");
    for (int i = 0; i < 100; ++i) {
        double mid = a / 2 + b / 2;
        if (mid == a || mid == b)
            break;
        double fm = f(mid);
        if (!isfinite(fm))
            throw invalid_argument("函数值必须有限");
        if (fm == 0)
            return mid;
        // 中点与左端同号时舍弃左半段，否则舍弃右半段。
        if ((fm < 0) == (fa < 0)) {
            a = mid;
            fa = fm;
        } else
            b = mid;
    }
    return a / 2 + b / 2;
}

#include <functional>
#include <cmath>
#include <stdexcept>
using namespace std;

double newton_method(double x0, function<double(double)> f, function<double(double)> df,
                     double eps = 1e-7, int max_iter = 100) {
    if (!isfinite(x0) || !isfinite(eps) || eps <= 0 || max_iter <= 0)
        throw invalid_argument("初值、误差或迭代次数无效");
    double x = x0;
    for (int i = 0; i < max_iter; ++i) {
        double fx = f(x);
        if (!isfinite(fx))
            throw runtime_error("函数值不有限");
        if (fabs(fx) <= eps)
            return x; // 返回前检查残差，而非只检查步长。
        double dfx = df(x);
        if (!isfinite(dfx) || dfx == 0)
            throw runtime_error("导数无效或为零");
        double next = x - fx / dfx;
        if (!isfinite(next) || next == x)
            throw runtime_error("迭代溢出或停滞");
        x = next;
    }
    if (isfinite(f(x)) && fabs(f(x)) <= eps)
        return x;
    throw runtime_error("达到迭代上限但残差仍超出阈值");
}

bool insert_BST(int value) {
    // 处理空树情况：直接创建根节点
    if (!root) {
        root = new TreeNode(value);
        return true;
    }

    TreeNode *cur = root;
    // 迭代查找合适的插入位置
    while (true) {
        if (value < cur->val) {
            // 值小于当前节点，向左子树查找
            if (cur->left)
                cur = cur->left; // 左子树非空，继续向下查找
            else {
                cur->left = new TreeNode(value); // 找到空位置，插入新节点
                return true;
            }
        } else if (value == cur->val) {
            return false; // 本笔记的 BST 不存重复值
        } else {
            // 值大于当前节点，向右子树查找
            if (cur->right)
                cur = cur->right; // 右子树非空，继续向下查找
            else {
                cur->right = new TreeNode(value); // 找到空位置，插入新节点
                return true;
            }
        }
    }
}

#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;

bool check(const vector<int> &piles, int k, int h) {
    ll hours = 0; // 用 long long 防止大数相加溢出
    for (int p : piles)
        hours += (1LL * p + k - 1) / k; // 等价于 ceil(p / k)，耗时累加
    return hours <= h;                  // 若总时间不超过 h，则速度可行
}

int minEatingSpeed(vector<int> &piles, int h) {
    int left = 1, right = *max_element(piles.begin(), piles.end());
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (check(piles, mid, h))
            right = mid; // mid 足够快，尝试更小的速度
        else
            left = mid + 1; // mid 对应的耗时过长，继续查找更高速度
    }
    return left; // 返回最小可行速度
}

#include <vector>
#include <algorithm>
#include <cmath>
#include <stdexcept>
using namespace std;

using ll = long long;

bool check(const vector<double> &a, double len, int k) {
    ll cnt = 0;
    for (double x : a)
        if (len <= 0)
            return false;
        else if (floor(x / len) >= k - cnt)
            return true;
        else
            cnt += static_cast<ll>(floor(x / len));
    return cnt >= k; // 总段数是否满足要求
}

double maxCutLength(const vector<double> &a, int k) {
    if (a.empty() || k <= 0)
        throw invalid_argument("木棒非空且 k > 0");
    double left = 0, right = *max_element(a.begin(), a.end());
    for (int i = 0; i < 100; ++i) {
        double mid = left + (right - left) / 2;
        if (mid == left || mid == right)
            break;
        long long count = 0;
        for (double x : a) {
            double pieces = floor(x / mid);
            if (pieces >= k - count) {
                count = k;
                break;
            }
            count += static_cast<long long>(pieces);
        }
        if (count >= k)
            left = mid;
        else
            right = mid;
    }
    return left;
}

#include <vector>
using namespace std;

using ll = long long;
bool check(const vector<int> &W, ll X, int M) {
    ll load = 0; // 当前工人的累计工作量
    int cnt = 1; // 已使用的工人数量（至少1个）
    for (int w : W) {
        if (w > X)
            return false; // 单个任务超过 X，直接不可能
        if (load + w > X) {
            cnt++;    // 新开一个工人
            load = w; // 新工人从当前任务开始
        } else
            load += w; // 当前工人继续承担任务
    }
    return cnt <= M; // 使用的工人数是否在限制内
}

ll minimizeMaxWorkload(vector<int> &W, int M) {
    ll left = 0, right = 0;
    for (int w : W) {
        if (w > left) left = w; // 上限至少要容纳最大的单个任务。
        right += w;            // 全部任务放一组，得到可行上界。
    }

    while (left < right) {
        ll mid = left + (right - left) / 2;
        if (check(W, mid, M))
            right = mid; // mid 可行，尝试更小的上限
        else
            left = mid + 1; // mid 对应的方案不可行，继续尝试更大上限
    }
    return left; // 返回最小可行最大工作量
}

#include <vector>
#include <algorithm>
using namespace std;

bool check(const vector<int> &x, int d, int C) {
    int cnt = 1;     // 已安置奶牛数量（第一头在x[0]）
    int last = x[0]; // 最后一头奶牛的安置位置
    for (int i = 1; i < x.size(); i++) {
        if (x[i] - last >= d) { // 满足最小间距要求
            cnt++;
            last = x[i]; // 更新最后安置位置
            if (cnt >= C)
                return true; // 已安置足够数量，提前返回
        }
    }
    return false; // 无法安置所有奶牛
}

int maxMinDistance(vector<int> &x, int C) {
    sort(x.begin(), x.end());                   // 预处理：排序牛栏位置
    int left = 0, right = x.back() - x.front(); // 最大可能间距

    while (left < right) {
        int mid = left + (right - left) / 2 + (right - left) % 2; // 取上中位数避免死循环
        if (check(x, mid, C))
            left = mid; // mid 可行，尝试更大的间距
        else
            right = mid - 1; // mid 不可行，缩小间距
    }
    return left; // 返回最大可行最小间距
}

#include <vector>
#include <algorithm>
#include <cmath>
#include <stdexcept>
using namespace std;

bool check(const vector<double> &area, double A, int people) {
    int cnt = 0;
    for (double x : area)
        if (A <= 0)
            return false;
        else if (floor(x / A) >= people - cnt)
            return true;
        else
            cnt += static_cast<int>(floor(x / A));
    return cnt >= people; // 总份数是否满足要求
}

double maxPieArea(const vector<int> &radii, int friends) {
    if (radii.empty() || friends < 0)
        throw invalid_argument("派非空且朋友数非负");
    long long people = 1LL * friends + 1;
    vector<double> area;
    for (int radius : radii)
        area.push_back(acos(-1.0) * radius * radius);
    double left = 0, right = *max_element(area.begin(), area.end());
    for (int i = 0; i < 100; ++i) {
        double mid = left + (right - left) / 2;
        if (mid == left || mid == right)
            break;
        long long count = 0;
        for (double x : area) {
            double pieces = floor(x / mid);
            if (pieces >= people - count) {
                count = people;
                break;
            }
            count += static_cast<long long>(pieces);
        }
        if (count >= people)
            left = mid;
        else
            right = mid;
    }
    return left;
}

// 伪代码：L/R 保存候选范围，check 计算当前候选值的判定结果。
/*
 * 二分答案通用模板
 *
 * 二分答案是一种基于单调性的高效搜索技术，通过二分查找确定满足条件的最优解。
 * 适用于求解最优化问题，如最大化最小值、最小化最大值等。
 */

using ll = long long;

/*
 * 检查函数 - 二分答案的核心
 *
 * 把候选值 x 代入判断，观察判定结果怎样随 x 变化：
 * - 对于最大化问题：若x满足条件，则所有≤x的值都满足
 * - 对于最小化问题：若x满足条件，则所有≥x的值都满足
 *
 * 参数 x：待检查的值
 * 返回：bool 检查结果
 *
 * 从一个可行方案出发，改变 x 后仍能复用该方案，就能推导可行方向。
 * 注意：实现要点: 根据具体问题设计高效的检查逻辑
 */
bool check(ll x) {
    // 判断 x 是否满足题目条件
    // 根据题目推导可行方向，再决定二分时缩短哪一侧。
    /*
     实际应用中除了上述示例的贪心遍历，可能更为复杂：

     二分 + BFS/DFS：判断连通性或最短路是否满足限制。

     二分 + 动态规划：判断是否存在满足条件的 DP 路径。

     二分 + 最大流：网络流问题中的容量判定。
     */
}

/*
 * 整数二分答案模板 - 最大化最小值类问题
 *
 * 适用于求解满足条件的最大值，如：最大最小间距、最大可行值等。
 * 单调性：若mid满足条件，则所有≤mid的值都满足，目标是找到最大的满足条件的值。
 *
 * 返回：ll 满足条件的最大值
 *
 * 注意：时间复杂度: O(log(R-L))
 * 注意：适用场景: 最大化最小值、寻找右边界
 * 注意：模板特点: 记录ans，l=mid+1，r=mid-1
 */
ll binary_search_maximize_min() {
    ll l = L, r = R, ans = -1;
    while (l <= r) {
        long long mid = l + (r - l) / 2;  // 防止溢出
        if (check(mid)) {                 // mid 能否满足要求
            ans = mid;                    // 记录可行答案
            l = mid + 1;                  // 继续尝试更大的值
        } else {
            r = mid - 1;                  // mid 不行，尝试更小的值
        }
    }
    return ans;
}

/*
 * 整数二分答案模板 - 最小化最大值类问题
 *
 * 适用于求解满足条件的最小值，如：最小最大工作量、最小可行值等。
 * 单调性：若mid满足条件，则所有≥mid的值都满足，目标是找到最小的满足条件的值。
 *
 * 返回：ll 满足条件的最小值
 *
 * 注意：时间复杂度: O(log(R-L))
 * 注意：适用场景: 最小化最大值、寻找左边界
 * 注意：模板特点: 不记录ans，r=mid，l=mid+1
 */
ll binary_search_minimize_max() {
    ll l = L, r = R;
    while (l < r) {
        long long mid = l + (r - l) / 2;  // 防止溢出
        if (check(mid)) {
            r = mid;                      // mid 可行，尝试更小的值
        } else {
            l = mid + 1;                  // mid 不可行，继续尝试更大的值
        }
    }
    return l;
}

/*
 * 浮点数二分答案模板
 *
 * 适用于实数范围内的二分答案，通过固定迭代次数或精度阈值控制搜索精度。
 * 常用于连续函数求根、数值计算等问题。
 *
 * 返回：double 满足条件的近似解
 *
 * 注意：时间复杂度: O(100) 或 O(log((R-L)/eps))
 * 注意：适用场景: 实数范围的最优化、连续函数求根
 * 注意：模板特点: 直接赋值mid，无±1操作
 */
double binary_search_real() {
    double l = L, r = R;
    // 方法1: 固定迭代次数（避免无限循环，仍须检查精度要求）
    for (int i = 0; i < 100; i++) {
        double mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;      // check 可行 → 在左半部分继续搜索
        } else {
            l = mid;      // check 不行 → 在右半部分继续搜索
        }
    }

    // 方法2: 精度控制
    // const double eps = 1e-7;
    // while (r - l > eps) {
    //     double mid = (l + r) / 2;
    //     if (check(mid)) {
    //         r = mid;
    //     } else {
    //         l = mid;
    //     }
    // }

    return l; // 或 (l + r) / 2
}

/*
 * 二分答案解题步骤
 *
 * 1. 确定搜索范围 [L, R]
 * 2. 设计检查函数 check(x)，确保单调性
 * 3. 根据问题类型选择合适的模板：
 *    - 最大化最小值 → binary_search_maximize_min
 *    - 最小化最大值 → binary_search_minimize_max
 *    - 实数范围问题 → binary_search_real
 * 4. 从可行方案的复用关系推导判定方向
 *
 * 注意：核心思想: 将最优化问题转化为判定性问题
 * 改变候选值后，已有方案仍能复用的方向就是可行方向
 * 注意：常见应用: 分配问题、调度问题、数值计算等
 */

#include <vector>
using namespace std;

const double eps = 1e-6; // 精度阈值

double poly_func(double x, vector<double> const &a, int n) {
    double result = a[0]; // 初始化为最高次项系数
    for (int i = 1; i <= n; ++i) {
        result = result * x + a[i]; // 秦九韶算法迭代
    }
    return result;
}

template <typename Func> double ternary_search_max(Func f, double l, double r) {
    // 方法1：固定迭代次数（避免无限循环，仍须检查精度要求）
    for (int i = 0; i < 100; ++i) {
        double k = (r - l) / 3.0;
        double mid1 = l + k; // 左三等分点
        double mid2 = r - k; // 右三等分点

        if (f(mid1) < f(mid2)) {
            l = mid1; // 最大值在[mid1, r]区间
        } else {
            r = mid2; // 最大值在[l, mid2]区间
        }
    }

    return (l + r) / 2.0; // 返回区间中点作为近似最优解
}

template <typename Func> double ternary_search_min(Func f, double l, double r) {
    for (int i = 0; i < 100; ++i) {
        double k = (r - l) / 3.0;
        double mid1 = l + k;
        double mid2 = r - k;

        if (f(mid1) > f(mid2)) { // 注意：这里比较符号与求最大值相反
            l = mid1;            // 最小值在[mid1, r]区间
        } else {
            r = mid2; // 最小值在[l, mid2]区间
        }
    }

    return (l + r) / 2.0;
}

// 示例函数为 f(x)=-(x-k)²+c。
#include <algorithm>
using namespace std;

using ll = long long;

ll k, c; // 抛物线参数：顶点在(k, c)

ll f(ll x) {
    ll diff = x - k;
    return -(diff * diff) + c; // 避免使用pow，提高效率
}

// 整数区间不能依赖无限缩小。
ll ternary_search(ll l, ll r) {
    // 边界检查
    if (l > r)
        return -1; // 无效区间

    // 特殊情况处理：区间长度很小直接暴力
    if (r - l + 1 <= 3) {
        ll best = l;
        for (ll x = l + 1; x <= r; x++) {
            if (f(x) > f(best))
                best = x;
        }
        return best;
    }

    // 三分阶段：不断缩小搜索区间
    while (r - l > 3) {            // 区间长度>3时继续三分
        ll mid1 = l + (r - l) / 3; // 左三等分点
        ll mid2 = r - (r - l) / 3; // 右三等分点

        // 比较两个三等分点的函数值
        if (f(mid1) < f(mid2))
            l = mid1; // 峰值在[mid1, r]区间
        else
            r = mid2; // 峰值在[l, mid2]区间
    }

    // 暴力阶段：枚举剩余的所有点
    ll best = l;
    for (ll x = l + 1; x <= r; x++) {
        if (f(x) > f(best))
            best = x;
    }

    return best;
}

// 这条抛物线在 k 处最高。
ll optimal_solution(ll l, ll r) {
    if (l > r)
        return -1;
    return max(l, min(r, k));
}

// ll 表示 long long；本函数比较峰形曲线上的两个取点，最后逐个检查剩余整数。
template <typename Func> ll integer_ternary_search(Func f, ll l, ll r) {
    while (r - l > 3) {
        ll mid1 = l + (r - l) / 3;
        ll mid2 = r - (r - l) / 3;

        if (f(mid1) < f(mid2))
            l = mid1;
        else
            r = mid2;
    }

    ll best = l;
    for (ll x = l + 1; x <= r; x++) {
        if (f(x) > f(best))
            best = x;
    }
    return best;
}