//generated by GPT-5.4, modified by hamamu
namespace FibonacciSearchSpace{
using ll  = long long;
using Int = long long;

template<class T,bool MINIMIZE,class F>
pair<T,Int> fibonacciSearchCore(F f,ll l,ll r,const T &worseValue){
    assert(l<=r);

    auto better=[&](const T &x,const T &y)->bool{ //true:xがyよりbetter
        if constexpr (MINIMIZE) return x<y;
        else                    return x>y;
    };
    auto get=[&](ll x)->T{ //区間外の点はダミー値を返すラッパー
        if(x<l || r<x) return worseValue;
        return f(x);
    };

    //---- 4点a,b,c,dを初期化
    /*
    d が r を初めて超えるまで、差分をフィボナッチ的に伸ばす。
    以後この回数だけ縮約すれば、b-c間距離が1になり探索終了する。
    */
    ll a=l-1, b=l, c=l+1, d=l+2;
    ll n=0;
    while(d<=r) b=c, c=d, d=b+c-a, ++n;

    //---- 縮約処理
    T yb=get(b), yc=get(c);
    for(ll i=0;i<n;++i){
        //-- ybがbetterなとき
        if(better(yb,yc)){
            //右側 d 寄りの領域を捨てて [a,b,c] 側を残す。
            d=c, c=b, b=a+d-c;
            yc=yb, yb=get(b);
        }
        //-- ycがbetterなとき
        else{
            //左側 a 寄りの領域を捨てて [b,c,d] 側を残す。
            a=b, b=c, c=a+d-b;
            yb=yc, yc=get(c);
        }
    }
    if(better(yb,yc)) return {yb,b};
    else              return {yc,c};
}

// ラムダ式f(ll)の戻り値型を自動で拾って T にするラッパー
template<bool MINIMIZE,class F>
auto fibonacciSearch(F f,ll l,ll r,
    const decay_t<invoke_result_t<F&, ll>> &worseValue)
{
    using T = decay_t<invoke_result_t<F&, ll>>;
    return fibonacciSearchCore<T,MINIMIZE>(f,l,r,worseValue);
}
}
using FibonacciSearchSpace::fibonacciSearch;
/*
- フィボナッチ探索: [l,r]の整数xに対しf(x)の最小/最大値を取得
auto f=[&](ll x) { return (x-5)*(x-5)+3; };
auto [mnf,mnx]=fibonacciSearch<true> (f,l,r,INF);  //最小化
auto [mxf,mxx]=fibonacciSearch<false>(f,l,r,-INF); //最大化

- 極値以外は"狭義"単調増加/減少であること(同点不可)
- 極値のみ同点複数可
- データ型Tは比較可能であればよい（単項マイナスは不要） pll,stringなども可
*/