Convex Hull Trick

/*
problems
https://codeforces.com/problemset/problem/311/B
https://codeforces.com/problemset/problem/1715/E 
/**/

struct line
	{
		ll m, c;
		line(ll x, ll y)
		{
			m = x;
			c = y;
		}
	};

	ll arr[100005];

	struct CHT
	{
		vector < line > vec;
		ll t, ptr;

		void init(ll x)
		{
			t = x;
			ptr = 0;
			vec.clear();
		}

		inline ll func(ll idx, ll x)
		{
			ll ret = vec[idx].m * x + vec[idx].c;

			return ret;
		}

		bool bad(line f1, line f2, line f3)
		{
			__int128 a = (f3.c - f1.c);
			a = a * (f1.m - f2.m);

			__int128 b = (f2.c - f1.c);
			b = b * (f1.m - f3.m);

			if(t == 1) return a <= b;
			if(t == 2) return a >= b;
			if(t == 3) return a >= b;
			if(t == 4) return a <= b;

			assert(0);
		}

		void add(line x)
		{
			ll sz = vec.size();
			while(sz >= 2 && bad(vec[sz - 2], vec[sz - 1], x))
			{
				vec.pop_back();
				sz--;
			}
			vec.push_back(x);
		}

		ll ask(ll x) // ternary search
		{
			if(vec.empty())
			{
				return 0;
			}

			ll lo = 0;
			ll hi = vec.size() - 1;

			ll ret = (t & 1)? mxlld : mnlld;

			while(lo <= hi)
			{
				ll mid1 = (lo + (hi - lo) / 3);
				ll mid2 = (hi - (hi - lo) / 3);

				ll ans1 = func(mid1,x);
				ll ans2 = func(mid2,x);

				if(ans1 > ans2)
				{
					if(t & 1)
					{
						ret = min(ret, ans2);
						lo = mid1 + 1;
					}
					else
					{
						ret = max(ret, ans1);
						hi = mid2 - 1;
					}
				}
				else
				{
					if(t & 1)
					{
						ret =  min(ret,ans1);
						hi = mid2 - 1;
					}
					else
					{
						ret = max(ret,ans2);
						lo = mid1 + 1;
					}
				}
			}
			return ret;
		}

		ll ask1(ll x) // pointer search (linear)
		{
			if(vec.empty())
			{
				return 0;
			}
			if(ptr >= vec.size()) ptr = vec.size() - 1;
			while(ptr < (vec.size() - 1))
			{
				if(t & 1)
				{
					if(func(ptr,x) > func(ptr + 1,x))
					{
						ptr++;
					}
					else break;
				}
				else
				{
					if(func(ptr,x) < func(ptr + 1,x))
					{
						ptr++;
					}
					else break;
				}
			}
			return func(ptr,x);
		}
	};
	// 1 = mi > mi+1, mn
	// 2 = mi > mi+1, mx
	// 3 = mi < mi+1, mn
	// 4 = mi < mi+1, mx
	
/////
/// my ac code for minimum query ... 

struct line
{
    int m, c ;
    line() {}
    line(int m,int c)
    {
        this->m=m ;
        this->c=c ;
    }
    int f(int x)
    {
        return x*m+c ;
    }
} tree[4*N] ;
 
void insert(line seg,int nd=1,int l=0,int r=n)
{
    if(l>=r)
    {
        return ;
    }
    if(l+1==r)
    {
        if(tree[nd].f(l)>seg.f(l))
        {
            tree[nd]=seg ;
        }
        return ;
    }
    int md=(l+r)/2 ;
    if(seg.f(md)<tree[nd].f(md))
    {
        swap(tree[nd],seg) ;
    }
    if(seg.f(l)<tree[nd].f(l))
    {
        insert(seg,nd*2,l,md) ;
    }
    else
    {
        insert(seg,nd*2+1,md+1,r) ;
    }
}
 
int query(int x,int nd=1,int l=0,int r=n)
{
    if(l+1==r)
    {
        return tree[nd].f(x) ;
    }
    int md=(l+r)/2, q1, q2=oo ;
    q1 = tree[nd].f(x) ;
    if(x<md)
    {
        q2 = query(x,nd*2,l,md) ;
    }
    else if(x>md)
    {
        q2 = query(x,nd*2+1,md+1,r) ;
    }
    return min(q1,q2) ;
}