namespace LC
{

vll line;
int getline(ll c)
{
    int k = 0, st = 20;
    while(st+1)
    {
        int now = k+(1<<st); st--;
        if(now >= line.size()) continue;
        
        if(line[now].fi*c+line[now].se < line[now-1].fi*c+line[now-1].se) k = now;
    }
    return k;
}
void pushline(pll C)
{
    while(line.size() >= 2)
    {
        pll A = line[line.size()-2];
        pll B = line.back();
        
        A = {A.fi-C.fi, A.se-C.se};
        B = {B.fi-C.fi, B.se-C.se};
        A.se = -A.se; B.se = -B.se;
        
        if(A.fi<0) A = {-A.fi, -A.se};
        if(B.fi<0) B = {-B.fi, -B.se};
        
        
        if(A.se*B.fi >= B.se*A.fi) line.pop_back();
        else break;
    }
    line.pb(C);
}

} // namespace LC