template<typename T>
struct line{
    T a, b;
    pair<T,T> sect;
    line(T a, T b):a(a), b(b), sect({a, b}){}
    T operator()(T x)const{return a*x + b;}
};
template<typename S> pair<S,S> intersect(const line<S> &a, const line<S> &b){if(b.a < a.a)return make_pair(b.b-a.b, a.a-b.a);else return make_pair(a.b-b.b, b.a-a.a);}
bool cmp_a = true;
template<typename T, typename cmp, long long inf = 1ll << 60 >
struct dynamic_convex_hull{
    dynamic_convex_hull(){};
    struct frac_cmp{bool operator()(const pair<T,T> &a, const pair<T,T> &b)const{return a.first == -inf ? true : (__int128)a.first * b.second <= (__int128)a.second * b.first;}};
    struct frac_less{bool operator()(const pair<T,T> &a, const pair<T,T> &b)const{return a.first == -inf ? true : (__int128)a.first * b.second < (__int128)a.second * b.first;}};
    struct line_cmp{
        bool operator()(const line<T> &a, const line<T> &b)const{
            return cmp_a ? cmp()(b.a, a.a) : frac_less()(a.sect, b.sect);
        }
    };
    set<line<T>, line_cmp> q;
    int size()const{return q.size();}
    void insert(line<T> l){
        cmp_a = true;
        auto it = q.find(l);
        if(it != q.end()){
            if(!cmp()(l.b, it->b))return;
            q.erase(it);
        }
        it = q.lower_bound(l);
        if(it == q.begin() || it == q.end() || !frac_cmp()(intersect(l, *it), intersect(*prev(it), l))){
            while(it != q.begin() and prev(it) != q.begin() and frac_cmp()(intersect(*prev(prev(it)), l), prev(it)->sect))q.erase(prev(it));
            while(it != q.end() and next(it) != q.end() and frac_cmp()(next(it)->sect, intersect(l, *it)))it = q.erase(it);
            if(it == q.begin())l.sect = make_pair(-inf, 1);
            else l.sect = intersect(*prev(it), l);
            q.insert(l);
            if(it != q.end()){
                line<T> tmp = *it;
                tmp.sect = intersect(l, tmp);
                q.erase(it);
                q.insert(tmp);
            }
        }
    }
    void insert(T a, T b){insert(line<T>(a, b));}
    T operator()(T x){
        cmp_a = false;
        return (*prev(q.upper_bound(line<T>(x, 1))))(x);
    }
    void clear(){q.clear();}
};