template<typename T>
struct line{
    T a, b;
    pair<T,T> sect;
    line(T a, T b):a(a), b(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);}
template<typename T, typename cmp>
struct convex_hull{
    convex_hull():h(0){};
    struct frac_cmp{bool operator()(const pair<T,T> &a, const pair<T,T> &b)const{return a.first * b.second <= a.second * b.first;}};
    int h;
    vector< line<T> > q;
    int size()const{return q.size()-h;}
    void push_back(line<T> l){
        if(!q.empty() and q.back().a == l.a)l.b = cmp()(l.b, q.back().b) ? l.b : q.back().b, q.pop_back();
        while(size() >= 2 and frac_cmp()(intersect(q[q.size()-2], l), q.back().sect))q.pop_back();
        if(!q.empty())l.sect = intersect(q.back(), l);
        q.emplace_back(l);
        // if((q.size()>>1)<= h)q.erase(q.begin(), q.begin()+h), h = 0;
    }
    void push_back(T a, T b){push_back(line<T>(a, b));}
    T operator()(T x){
        while(size() >= 2 and !cmp()(q[h](x), q[h+1](x)))++h;
        return q[h](x);
    }
    void clear(){h = 0, q.clear();}
};