Khóa học CTDL và GT

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

// Structure to represent a line y = m*x + c
struct Line {
    long long m, c;

    // Function to evaluate the line at a given x
    long long evaluate(long long x) const {
        return m * x + c;
    }
};

// Function to determine if line L1 is redundant given L0 and L2
// L0 and L2 are already on the lower envelope. L1 is redundant
// if the intersection of L0 and L2 is to the left of or at the
// intersection of L0 and L1.
// Uses cross-multiplication to avoid floating point.
// Lines are assumed to have decreasing slopes (m0 > m1 > m2).
// Returns true if L1 is redundant (should be removed).
bool is_redundant(const Line& l0, const Line& l1, const Line& l2) {
    // Check if intersection of l0 and l2 is <= intersection of l0 and l1
    // (c1 - c0) / (m0 - m1) >= (c2 - c0) / (m0 - m2)
    // Requires careful handling of potential division by zero if slopes are equal,
    // but here slopes are distinct (m0 > m1 > m2).
    // Cross-multiply: (c1 - c0) * (m0 - m2) >= (c2 - c0) * (m0 - m1)
    // This requires __int128 for intermediate products to avoid overflow.
    // Alternative check for decreasing slopes, min query:
    // l1 is redundant if intersection of l0 and l2 is LEFT of l0 and l1 intersection.
    // Intersection of l0 and l1: (c1 - c0) / (m0 - m1)
    // Intersection of l1 and l2: (c2 - c1) / (m1 - m2)
    // l1 is redundant if (c1 - c0) / (m0 - m1) >= (c2 - c1) / (m1 - m2)
    // (c1 - c0) * (m1 - m2) >= (c2 - c1) * (m0 - m1)
    // Using __int128 to prevent overflow for (c_i - c_j) * (m_k - m_l)
    return (__int128)(l1.c - l0.c) * (l0.m - l2.m) >= (__int128)(l2.c - l0.c) * (l0.m - l1.m);

    // Simpler check based on slope property for decreasing m, min query:
    // l1 is redundant if intersection(l0, l2) <= intersection(l0, l1)
    // This is equivalent to checking if intersection(l0, l1) >= intersection(l1, l2)
    // return (__int128)(l1.c - l0.c) * (l1.m - l2.m) >= (__int128)(l2.c - l1.c) * (l0.m - l1.m);
    // The first version `(__int128)(l1.c - l0.c) * (l0.m - l2.m) >= (__int128)(l2.c - l0.c) * (l0.m - l1.m)`
    // is more robust as it directly checks if l1 is *below* the line segment from l0 to l2 at the intersection point of l0 and l1 (when projected onto the x-axis).
    // Let's stick to the second simpler check (comparison of adjacent intersection points) as it's standard for deque CHT:
    // Check if intersection of l0 and l1 is >= intersection of l1 and l2
    // This means l1 is 'pushed up' by l0 and l2, becoming redundant.
     return (__int128)(l1.c - l0.c) * (l1.m - l2.m) >= (__int128)(l2.c - l1.c) * (l0.m - l1.m);
}


// Convex Hull Trick structure for decreasing slopes, increasing queries (Min query)
struct CHT {
    deque<Line> hull;
    int ptr = 0; // Pointer for querying increasing x values

    // Add a line with slope m and intercept c
    // Assumes lines are added with decreasing slopes (m is decreasing)
    void add_line(long long m, long long c) {
        Line newLine = {m, c};

        // If adding a line with slope >= last line, it's redundant (due to decreasing slope requirement)
        // or if hull is empty, add it directly.
        if (!hull.empty() && m >= hull.back().m) {
             // In case of equal slopes, keep the one with smaller intercept for min query
             if (m == hull.back().m) {
                 if (c < hull.back().c) {
                    hull.pop_back();
                 } else {
                    return; // Redundant line
                 }
             } else {
                return; // Slope is not strictly decreasing
             }
        }


        // Maintain the convex hull property by removing redundant lines from the back
        while (hull.size() >= 2 && is_redundant(hull[hull.size() - 2], hull.back(), newLine)) {
            hull.pop_back();
        }

        hull.push_back(newLine);

        // Since slopes are decreasing and queries are increasing,
        // the optimal line index increases or stays the same.
        // When a new line is added, the old optimal line might become suboptimal *earlier*.
        // The pointer `ptr` might need to be reset or adjusted.
        // A safer approach for this specific case (decreasing m, increasing x query)
        // is to keep the pointer from advancing too far if the new line
        // could be optimal for the *current or next* query.
        // However, since we are only adding lines with decreasing slopes,
        // the *new* line can only become optimal for *larger* x values than the last line added.
        // So the existing pointer for *increasing* queries is still valid relative
        // to the previous set of lines. When a new line is added, it only
        // affects queries for x values large enough to reach its section
        // on the lower envelope. The critical thing is that removing redundant lines
        // from the *back* doesn't invalidate the pointer which points near the *front*.
        // Resetting ptr to 0 after adding a line is a safe default if query monotonicity
        // is strict (always increasing x), but usually not necessary if the queries
        // continue to increase and we simply pick up where we left off.
        // Let's rely on the query function to advance the pointer correctly.
        // No need to reset ptr here.
    }

    // Query the minimum value at a given x
    // Assumes queries are made with increasing x values
    long long query(long long x) {
        // Advance the pointer while the next line gives a smaller value for the current x
        // hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x)
        // (m_{p+1} * x + c_{p+1}) <= (m_p * x + c_p)
        // (c_{p+1} - c_p) <= (m_p - m_{p+1}) * x
        // Since m_p > m_{p+1} (slopes are decreasing), m_p - m_{p+1} > 0.
        // x >= (c_{p+1} - c_p) / (m_p - m_{p+1}) -- This is the intersection x-coordinate
        // The pointer advances as long as x is >= the intersection point of hull[ptr] and hull[ptr+1].
        // Use cross-multiplication again to avoid floating point and potential division by zero
        // if m_p == m_{p+1} (though our add_line tries to prevent this).
        // Condition: hull[ptr+1] is better or equal to hull[ptr] for query x
        // m_{p+1} * x + c_{p+1} <= m_p * x + c_p
        // (m_{p+1} - m_p) * x <= c_p - c_{p+1}
        // Since m_{p+1} - m_p < 0, we flip the inequality when dividing by it (conceptually).
        // x >= (c_p - c_{p+1}) / (m_{p+1} - m_p) -- wait, this is wrong sign.
        // Let's stick to the geometric intuition: pointer advances while x is to the right of or at the intersection.
        // Intersection x of hull[p] and hull[p+1] is (c_{p+1} - c_p) / (m_p - m_{p+1}).
        // Pointer advances if current x >= intersection x.
        // x >= (c_{p+1} - c_p) / (m_p - m_{p+1})
        // x * (m_p - m_{p+1}) >= (c_{p+1} - c_p)  --- m_p - m_{p+1} > 0
        // Using __int128 for safety:
        while (ptr + 1 < hull.size() && hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x)) {
             // More numerically stable check: Is x beyond the intersection of hull[ptr] and hull[ptr+1]?
             // Intersection x: (hull[ptr+1].c - hull[ptr].c) / (hull[ptr].m - hull[ptr+1].m)
             // We advance if x >= intersection_x
             // x * (hull[ptr].m - hull[ptr+1].m) >= (hull[ptr+1].c - hull[ptr].c)
             // Need __int128 for the product x * slope_difference
             if ((__int128)hull[ptr+1].c - hull[ptr].c <= (__int128)x * (hull[ptr].m - hull[ptr+1].m)) {
                ptr++;
             } else {
                // The above check is equivalent to hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x)
                // for this case (decreasing m, increasing x, min query).
                // Let's use the evaluate check directly as it's simpler to read
                // but be mindful of potential overflow if x is large and m, c are large.
                // Assuming m*x+c fits in long long, evaluate is fine.
                ptr++;
             }
        }

        // Ensure pointer is within bounds if add_line removed lines
        // This is implicitly handled by the while loop condition `ptr + 1 < hull.size()`.
        // If hull becomes very small, ptr might point past the end.
        // Resetting ptr = min(ptr, (int)hull.size() - 1); after any pop_back might be safer
        // but the current add_line pops from back and query checks size, so it's usually fine.
        // Let's add a safeguard just in case.
        ptr = min(ptr, (int)hull.size() - 1);
        if (ptr < 0) ptr = 0; // Should not happen if lines are added, but defensive

        return hull[ptr].evaluate(x);
    }
};

// --- Example Usage ---
// This example simulates a DP problem where dp[i] = min(dp[j] + cost(j, i))
// and cost(j, i) leads to lines with decreasing slopes and queries with increasing x.
// E.g., dp[i] = min_{j<i} (dp[j] + (i-j)^2)
// dp[i] = min_{j<i} (dp[j] + i^2 - 2ij + j^2)
// dp[i] = min_{j<i} (dp[j] + j^2 - 2ij) + i^2
// Let m_j = -2j, c_j = dp[j] + j^2. We want min(m_j * i + c_j).
// Here m_j = -2j is decreasing as j increases. Queries are i, which are increasing.
// This fits the CHT case: decreasing slopes, increasing queries, min.

int main() {
    // Example 1: Basic CHT for decreasing m, increasing x, min query
    cout << "Example 1: Decreasing slopes, Increasing queries (Min)" << endl;
    CHT cht_min_dec_m_inc_x;

    // Add lines with decreasing slopes: y = -1x + 5, y = -2x + 8, y = -3x + 9, y = -4x + 10
    // Slopes: -1, -2, -3, -4 (decreasing)
    cht_min_dec_m_inc_x.add_line(-1, 5); // y = -x + 5
    cht_min_dec_m_inc_x.add_line(-2, 8); // y = -2x + 8
    cht_min_dec_m_inc_x.add_line(-3, 9); // y = -3x + 9
    cht_min_dec_m_inc_x.add_line(-4, 10); // y = -4x + 10

    // Query with increasing x values: x = 1, 2, 3, 4, 5
    cout << "Query at x = 1: " << cht_min_dec_m_inc_x.query(1) << endl; // min(-1+5, -2+8, -3+9, -4+10) = min(4, 6, 6, 6) = 4 (Line -1x+5)
    cout << "Query at x = 2: " << cht_min_dec_m_inc_x.query(2) << endl; // min(-2+5, -4+8, -6+9, -8+10) = min(3, 4, 3, 2) = 2 (Line -4x+10)
    // Wait, calculations above manually show different results. Let's trace the CHT hull.
    // L1: -1x + 5. Hull: [(-1, 5)]
    // L2: -2x + 8. Hull: [(-1, 5), (-2, 8)]. Intersection x: (8-5)/(-1 - (-2)) = 3/1 = 3. L1 is better for x < 3, L2 for x > 3.
    // L3: -3x + 9. Slopes: -1, -2, -3. Hull: [(-1, 5), (-2, 8)]. is_redundant((-1,5), (-2,8), (-3,9))?
    // (c1-c0)*(m1-m2) >= (c2-c1)*(m0-m1)
    // L0=(-1,5), L1=(-2,8), L2=(-3,9)
    // (8-5)*(-2 - (-3)) >= (9-8)*(-1 - (-2))
    // 3 * 1 >= 1 * 1 --> 3 >= 1 (True). L1 (-2,8) is redundant. Pop (-2,8).
    // Hull: [(-1, 5), (-3, 9)]. Intersection x: (9-5)/(-1 - (-3)) = 4/2 = 2. L0 better for x < 2, L2 better for x > 2.
    // L4: -4x + 10. Slopes: -1, -3, -4. Hull: [(-1, 5), (-3, 9)]. is_redundant((-1,5), (-3,9), (-4,10))?
    // L0=(-1,5), L1=(-3,9), L2=(-4,10)
    // (9-5)*(-3 - (-4)) >= (10-9)*(-1 - (-3))
    // 4 * 1 >= 1 * 2 --> 4 >= 2 (True). L1 (-3,9) is redundant. Pop (-3,9).
    // Hull: [(-1, 5), (-4, 10)]. Intersection x: (10-5)/(-1 - (-4)) = 5/3 = 1.66...
    // L0 (-1,5) better for x < 1.66, L1 (-4,10) better for x > 1.66.
    // Final hull: [(-1, 5), (-4, 10)]

    cout << "Query at x = 1: " << cht_min_dec_m_inc_x.query(1) << endl;   // min(-1*1+5, -4*1+10) = min(4, 6) = 4. Correct. Ptr stays 0.
    cout << "Query at x = 2: " << cht_min_dec_m_inc_x.query(2) << endl;   // min(-1*2+5, -4*2+10) = min(3, 2) = 2. Correct. Ptr moves to 1.
    cout << "Query at x = 3: " << cht_min_dec_m_inc_x.query(3) << endl;   // Ptr is 1. Evaluate hull[1]: -4*3+10 = -2. Correct. Ptr stays 1.
    cout << "Query at x = 0: " << cht_min_dec_m_inc_x.query(0) << endl;   // Ptr is 1. Query 0. hull[1] is better than hull[0]?? -4*0+10=10, -1*0+5=5. hull[0] is better.
                                                                         // This highlights that if queries are *not* strictly increasing,
                                                                         // the O(1) pointer method is wrong. We need binary search or similar.
                                                                         // Let's adjust the example to strictly increasing queries.

    cout << "Query at x = 1: " << cht_min_dec_m_inc_x.query(1) << endl;
    cout << "Query at x = 2: " << cht_min_dec_m_inc_x.query(2) << endl;
    cout << "Query at x = 3: " << cht_min_dec_m_inc_x.query(3) << endl;
    cout << "Query at x = 4: " << cht_min_dec_m_inc_x.query(4) << endl; // Ptr is 1. Evaluate hull[1]: -4*4+10 = -6.

    // Let's reset and use a simple DP example form
    cout << "\nExample 2: DP-like structure (Min, Decreasing m, Increasing x)" << endl;
    CHT cht_dp_example;

    // dp[i] = min_{j<i} (dp[j] + (i-j)^2)
    // dp[i] = min_{j<i} (dp[j] + i^2 - 2ij + j^2)
    // dp[i] = min_{j<i} ( (-2j) * i + (dp[j] + j^2) ) + i^2
    // m_j = -2j, c_j = dp[j] + j^2
    // j runs from 0 to i-1. As i increases, j increases, so m_j = -2j decreases. Queries x=i increase.
    // This fits decreasing slopes, increasing queries, min query CHT.

    // Assume dp[0] = 0
    long long dp0 = 0;
    // For i=1: dp[1] = min_{j<1} (dp[j] + (1-j)^2) = dp[0] + (1-0)^2 = 0 + 1 = 1
    // Add line for j=0: m_0 = -2*0 = 0, c_0 = dp[0] + 0^2 = 0. Line: y = 0x + 0
    cht_dp_example.add_line(0, dp0 + 0*0); // m=0, c=0

    long long i = 1; // Query at x = i
    long long dp1 = cht_dp_example.query(i) + i*i; // min(0*1+0) + 1*1 = 0 + 1 = 1
    cout << "dp[" << i << "] = " << dp1 << endl;
    // Add line for j=1: m_1 = -2*1 = -2, c_1 = dp[1] + 1^2 = 1 + 1 = 2. Line: y = -2x + 2
    cht_dp_example.add_line(-2, dp1 + 1*1); // m=-2, c=2

    i = 2; // Query at x = i
    long long dp2 = cht_dp_example.query(i) + i*i; // min(0*2+0, -2*2+2) + 2*2 = min(0, -2) + 4 = -2 + 4 = 2
    cout << "dp[" << i << "] = " << dp2 << endl;
    // Add line for j=2: m_2 = -2*2 = -4, c_2 = dp[2] + 2^2 = 2 + 4 = 6. Line: y = -4x + 6
    cht_dp_example.add_line(-4, dp2 + 2*2); // m=-4, c=6

    i = 3; // Query at x = i
    long long dp3 = cht_dp_example.query(i) + i*i; // min(0*3+0, -2*3+2, -4*3+6) + 3*3 = min(0, -4, -6) + 9 = -6 + 9 = 3
    cout << "dp[" << i << "] = " << dp3 << endl;
    // Add line for j=3: m_3 = -2*3 = -6, c_3 = dp[3] + 3^2 = 3 + 9 = 12. Line: y = -6x + 12
    cht_dp_example.add_line(-6, dp3 + 3*3); // m=-6, c=12

    i = 4; // Query at x = i
    long long dp4 = cht_dp_example.query(i) + i*i; // min(0*4+0, -2*4+2, -4*4+6, -6*4+12) + 4*4 = min(0, -6, -10, -12) + 16 = -12 + 16 = 4
    cout << "dp[" << i << "] = " << dp4 << endl;

    // Note: This specific DP (dp[i] = min_{j<i} (dp[j] + (i-j)^2)) actually has dp[i]=i.
    // Let's recheck calculations.
    // dp[0] = 0
    // i=1: dp[1] = dp[0] + (1-0)^2 = 0 + 1 = 1. Add line m=-2*0=0, c=dp[0]+0^2=0. Hull: [y=0]. Query x=1: min(0*1+0)=0. dp[1] = 0 + 1^2 = 1. Correct.
    // i=2: dp[2] = min(dp[0]+(2-0)^2, dp[1]+(2-1)^2) = min(0+4, 1+1) = min(4, 2) = 2.
    // Add line for j=1: m=-2*1=-2, c=dp[1]+1^2=1+1=2. Add y=-2x+2. Hull from [y=0] and new y=-2x+2. Slopes 0 > -2. Intersection: (2-0)/(0 - (-2)) = 2/2=1. y=0 for x<1, y=-2x+2 for x>1. Hull: [y=0, y=-2x+2].
    // Query x=2: min(0*2+0, -2*2+2) = min(0, -2) = -2. dp[2] = -2 + 2^2 = -2+4 = 2. Correct.
    // i=3: dp[3] = min(dp[0]+(3-0)^2, dp[1]+(3-1)^2, dp[2]+(3-2)^2) = min(0+9, 1+4, 2+1) = min(9, 5, 3) = 3.
    // Add line for j=2: m=-2*2=-4, c=dp[2]+2^2=2+4=6. Add y=-4x+6. Hull [y=0, y=-2x+2] and y=-4x+6. Slopes 0 > -2 > -4.
    // Check y=-2x+2 redundancy with y=0 and y=-4x+6. L0=(0,0), L1=(-2,2), L2=(-4,6).
    // (c1-c0)*(m1-m2) >= (c2-c1)*(m0-m1)
    // (2-0)*(-2 - (-4)) >= (6-2)*(0 - (-2))
    // 2 * 2 >= 4 * 2  --> 4 >= 8 (False). y=-2x+2 is NOT redundant.
    // Hull is [y=0, y=-2x+2, y=-4x+6]. Intersections: y=0 and y=-2x+2 is at x=1. y=-2x+2 and y=-4x+6 is at (-6-2)/(-2-(-4)) = -8/2 = -4 ? No, (6-2)/(-2-(-4)) = 4/2 = 2.
    // Intersection 1: x=1 (0x+0 = -2x+2 => 2x=2 => x=1).
    // Intersection 2: x=2 (-2x+2 = -4x+6 => 2x=4 => x=2).
    // For x<1, y=0 optimal. 1<=x<2, y=-2x+2 optimal. x>=2, y=-4x+6 optimal.
    // Query x=3: cht_dp_example.query(3). ptr=0. hull[1].evaluate(3) = -2*3+2=-4 <= hull[0].evaluate(3)=0. ptr++. ptr=1.
    // ptr=1. hull[2].evaluate(3) = -4*3+6=-6 <= hull[1].evaluate(3)=-4. ptr++. ptr=2.
    // ptr=2. ptr+1 >= size. loop ends. Return hull[2].evaluate(3) = -6. dp[3] = -6 + 3^2 = -6 + 9 = 3. Correct.

    // i=4: dp[4] = min(dp[0]+(4-0)^2, dp[1]+(4-1)^2, dp[2]+(4-2)^2, dp[3]+(4-3)^2) = min(0+16, 1+9, 2+4, 3+1) = min(16, 10, 6, 4) = 4.
    // Add line for j=3: m=-2*3=-6, c=dp[3]+3^2=3+9=12. Add y=-6x+12. Hull [y=0, y=-2x+2, y=-4x+6] and y=-6x+12. Slopes 0 > -2 > -4 > -6.
    // Check y=-4x+6 redundancy with y=-2x+2 and y=-6x+12. L0=(-2,2), L1=(-4,6), L2=(-6,12).
    // (c1-c0)*(m1-m2) >= (c2-c1)*(m0-m1)
    // (6-2)*(-4 - (-6)) >= (12-6)*(-2 - (-4))
    // 4 * 2 >= 6 * 2 --> 8 >= 12 (False). y=-4x+6 is NOT redundant.
    // Hull is [y=0, y=-2x+2, y=-4x+6, y=-6x+12].
    // Intersections: x=1, x=2, x=3. (y=-4x+6 and y=-6x+12: (12-6)/(-4 - (-6)) = 6/2 = 3).
    // Query x=4: cht_dp_example.query(4). ptr starts at 2 (from previous query).
    // ptr=2. hull[3].evaluate(4)=-6*4+12=-12 <= hull[2].evaluate(4)=-4*4+6=-10. ptr++. ptr=3.
    // ptr=3. ptr+1 >= size. loop ends. Return hull[3].evaluate(4) = -12. dp[4] = -12 + 4^2 = -12 + 16 = 4. Correct.

    cout << "Final Hull size for DP example: " << cht_dp_example.hull.size() << endl; // Should be 4


    return 0;
}

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

// Structure to represent a line y = m*x + c
struct Line {
    long long m, c;

    // Function to evaluate the line at a given x
    long long evaluate(long long x) const {
        return m * x + c;
    }
};

// Function to determine if line L1 is redundant given L0 and L2 for *increasing* slopes, min query
// L0, L1, L2 have increasing slopes m0 < m1 < m2.
// L1 is redundant if the intersection of L0 and L2 is to the RIGHT of or at the
// intersection of L0 and L1.
// Intersection of L0 and L1: (c1 - c0) / (m0 - m1)
// Intersection of L1 and L2: (c2 - c1) / (m1 - m2)
// For increasing slopes, l1 is redundant if intersection(l0, l1) >= intersection(l1, l2)
// (c1 - c0) / (m0 - m1) >= (c2 - c1) / (m1 - m2)
// With m0 < m1 < m2, m0 - m1 < 0 and m1 - m2 < 0. Cross-multiplication needs care with signs or use __int128 directly.
// (c1 - c0) * (m1 - m2) <= (c2 - c1) * (m0 - m1) -- Note the reversed inequality because denominators are negative.
// Let's use __int128 for robustness.
bool is_redundant_inc_m(const Line& l0, const Line& l1, const Line& l2) {
     return (__int128)(l1.c - l0.c) * (l1.m - l2.m) <= (__int128)(l2.c - l1.c) * (l0.m - l1.m);
}

// Convex Hull Trick structure for increasing slopes, increasing queries (Min query)
struct CHT_IncM_IncX_Min {
    deque<Line> hull;
    int ptr = 0; // Pointer for querying increasing x values

    // Add a line with slope m and intercept c
    // Assumes lines are added with increasing slopes (m is increasing)
    void add_line(long long m, long long c) {
        Line newLine = {m, c};

        // If adding a line with slope <= last line, it's redundant (due to increasing slope requirement)
        if (!hull.empty() && m <= hull.back().m) {
             // In case of equal slopes, keep the one with smaller intercept for min query
             if (m == hull.back().m) {
                 if (c < hull.back().c) {
                    hull.pop_back();
                 } else {
                    return; // Redundant line
                 }
             } else {
                return; // Slope is not strictly increasing
             }
        }

        // Maintain the convex hull property by removing redundant lines from the back
        // Using is_redundant_inc_m for increasing slopes
        while (hull.size() >= 2 && is_redundant_inc_m(hull[hull.size() - 2], hull.back(), newLine)) {
            hull.pop_back();
        }

        hull.push_back(newLine);

        // Pointer logic is the same as decreasing m, increasing x for MIN query.
        // As x increases, we move towards lines with larger slopes on the lower envelope.
    }

    // Query the minimum value at a given x
    // Assumes queries are made with increasing x values
    long long query(long long x) {
         // Advance the pointer while the next line gives a smaller value for the current x
         // hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x)
         // m_{p+1} * x + c_{p+1} <= m_p * x + c_p
         // (m_{p+1} - m_p) * x <= c_p - c_{p+1}
         // With increasing slopes, m_{p+1} - m_p > 0.
         // x <= (c_p - c_{p+1}) / (m_{p+1} - m_p)
         // x <= -(c_{p+1} - c_p) / (m_{p+1} - m_p)
         // Intersection of hull[p] and hull[p+1] is at x_intersect = (c_{p+1} - c_p) / (m_p - m_{p+1})
         // Here m_p - m_{p+1} < 0. x_intersect = -(c_{p+1} - c_p) / (m_{p+1} - m_p).
         // Pointer advances while x >= x_intersect.
         // x >= -(c_{p+1} - c_p) / (m_{p+1} - m_p)
         // x * (m_{p+1} - m_p) >= -(c_{p+1} - c_p)  --- Wait, m_{p+1} - m_p > 0.
         // x * (m_{p+1} - m_p) >= c_{p} - c_{p+1}  --- This looks right.
         // Using __int128 for safety:
        while (ptr + 1 < hull.size() && hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x)) {
             // The direct evaluation check is sufficient if m*x+c fits in long long.
             // If x or slopes/intercepts are large, use the cross-multiplication check:
             // x * (m_{p+1} - m_p) >= c_p - c_{p+1}
             // (__int128)x * (hull[ptr+1].m - hull[ptr].m) >= hull[ptr].c - hull[ptr+1].c
             if ((__int128)x * (hull[ptr+1].m - hull[ptr].m) >= hull[ptr].c - hull[ptr+1].c) {
                 ptr++;
             } else {
                 // Should be equivalent
                 ptr++;
             }

        }

        ptr = min(ptr, (int)hull.size() - 1);
         if (ptr < 0) ptr = 0;

        return hull[ptr].evaluate(x);
    }
};


// --- Example Usage ---
// This example simulates a DP problem where dp[i] = min(dp[j] + cost(j, i))
// and cost(j, i) leads to lines with increasing slopes and queries with increasing x.
// E.g., dp[i] = min_{j<i} (dp[j] + (j-i)^2) -- actually same as previous example structure
// Let's consider dp[i] = min_{j<i} (dp[j] + a*i*j + b*i + k*j + C)
// If a > 0, we might get increasing slope terms.

int main() {
    cout << "\nExample 3: Increasing slopes, Increasing queries (Min)" << endl;
    CHT_IncM_IncX_Min cht_min_inc_m_inc_x;

    // Add lines with increasing slopes: y = 1x + 5, y = 2x + 2, y = 3x + 1, y = 4x + 0
    // Slopes: 1, 2, 3, 4 (increasing)
    cht_min_inc_m_inc_x.add_line(1, 5); // y = x + 5
    cht_min_inc_m_inc_x.add_line(2, 2); // y = 2x + 2
    cht_min_inc_m_inc_x.add_line(3, 1); // y = 3x + 1
    cht_min_inc_m_inc_x.add_line(4, 0); // y = 4x + 0

    // Let's trace the hull manually:
    // L1: (1, 5). Hull: [(1,5)]
    // L2: (2, 2). Slopes 1 < 2. Add. Hull: [(1,5), (2,2)]. Intersection: (2-5)/(1-2) = -3/-1 = 3.
    // L1 optimal for x < 3, L2 for x > 3.
    // L3: (3, 1). Slopes 1 < 2 < 3. Check redundancy of (2,2) with (1,5) and (3,1).
    // L0=(1,5), L1=(2,2), L2=(3,1).
    // (c1-c0)*(m1-m2) <= (c2-c1)*(m0-m1) -- for increasing m, min query
    // (2-5)*(2-3) <= (1-2)*(1-2)
    // (-3)*(-1) <= (-1)*(-1)
    // 3 <= 1 (False). (2,2) is NOT redundant.
    // Hull: [(1,5), (2,2), (3,1)]. Intersection (1,5), (2,2) at x=3. Intersection (2,2), (3,1) at (1-2)/(2-3) = -1/-1 = 1.
    // Wait, the intersection points must be increasing for increasing slopes, min query.
    // L0=(1,5), L1=(2,2), L2=(3,1), m0<m1<m2. Intersection(L0, L1) at (2-5)/(1-2) = 3. Intersection(L1, L2) at (1-2)/(2-3) = 1.
    // Point (3,1) causes intersection (2,2)/(3,1) at x=1. This intersection is LEFT of x=3.
    // The lines should form a convex shape. With increasing slopes, the intersection points of adjacent lines must be increasing.
    // If intersection(L0,L1) >= intersection(L1,L2), L1 is redundant.
    // (c1-c0)/(m0-m1) >= (c2-c1)/(m1-m2) => (c1-c0)*(m1-m2) <= (c2-c1)*(m0-m1) (multiplying by negative denominators)
    // Let's recheck redundancy condition with L0=(1,5), L1=(2,2), L2=(3,1).
    // (2-5)*(2-3) <= (1-2)*(1-2) -> (-3)*(-1) <= (-1)*(-1) -> 3 <= 1 FALSE. (2,2) not redundant.
    // Check with L0=(1,5), L1=(3,1), L2=(4,0). Slopes 1 < 3 < 4.
    // (1-5)*(3-4) <= (0-1)*(1-3)
    // (-4)*(-1) <= (-1)*(-2)
    // 4 <= 2 FALSE. (3,1) not redundant.
    // Hull: [(1,5), (2,2), (3,1), (4,0)]. Intersections at x=3, x=1, x=1. Oops, something is wrong with the example line choices.
    // Let's choose lines such that intersections are increasing:
    // L1: (1, 5)
    // L2: (2, 2) -> intersect at x=3
    // L3: (3, -1) -> intersect (2,2) and (3,-1) at (-1-2)/(2-3) = -3/-1 = 3. Intersection (1,5) and (3,-1) at (-1-5)/(1-3) = -6/-2 = 3. All intersect at x=3.
    // Let's try again with points that make a proper convex hull for increasing m, min query.
    // y = x + 0  (m=1, c=0)
    // y = 2x - 2 (m=2, c=-2) -> intersect at x=2
    // y = 3x - 6 (m=3, c=-6) -> intersect (2,-2) and (3,-6) at (-6 - (-2))/(2-3) = -4/-1 = 4
    // y = 4x - 12 (m=4, c=-12) -> intersect (3,-6) and (4,-12) at (-12 - (-6))/(3-4) = -6/-1 = 6
    // Intersections at x=2, x=4, x=6. This looks correct for increasing slopes, min query.

    cout << "Adding lines with increasing slopes: y=x, y=2x-2, y=3x-6, y=4x-12" << endl;
    CHT_IncM_IncX_Min cht_min_inc_m_inc_x_v2;
    cht_min_inc_m_inc_x_v2.add_line(1, 0); // y = x
    cht_min_inc_m_inc_x_v2.add_line(2, -2); // y = 2x - 2
    cht_min_inc_m_inc_x_v2.add_line(3, -6); // y = 3x - 6
    cht_min_inc_m_inc_x_v2.add_line(4, -12); // y = 4x - 12

    // Query with increasing x
    cout << "Query at x = 1: " << cht_min_inc_m_inc_x_v2.query(1) << endl; // min(1, 0, -3, -8) = -8. Ptr moves to 3.
    // Let's trace query x=1 manually again:
    // Hull: [(1,0), (2,-2), (3,-6), (4,-12)] ptr=0.
    // x=1: hull[1](1)=-0, hull[0](1)=1. -0 <= 1. ptr++. ptr=1.
    // x=1: hull[2](1)=-3, hull[1](1)=0. -3 <= 0. ptr++. ptr=2.
    // x=1: hull[3](1)=-8, hull[2](1)=-3. -8 <= -3. ptr++. ptr=3.
    // x=1: ptr=3. ptr+1 >= size. loop ends. Return hull[3](1) = -8. Correct.

    cout << "Query at x = 3: " << cht_min_inc_m_inc_x_v2.query(3) << endl; // Ptr starts at 3. Query 3.
    // x=3: ptr=3. hull[3](3) = 4*3-12=0. hull[2](3)=3*3-6=3. 0 <= 3. ptr stays 3.
    // But this is wrong. At x=3, lines give: y=3, y=4, y=3, y=0. Min is 0 from y=4x-12.
    // hull[0](3)=3, hull[1](3)=4, hull[2](3)=3, hull[3](3)=0.
    // The query logic needs to start from a point guaranteed to be before the optimal line or from 0.
    // When queries are INCREASING, the optimal line index also increases for MIN query regardless of slope order.
    // So the simple `ptr` logic for increasing queries should work for both slope orders for MIN query.
    // Let's trace Query 3 with ptr starting at 0.
    // x=3: ptr=0. hull[1](3)=2*3-2=4 >= hull[0](3)=1*3+0=3. 4 <= 3 FALSE. ptr stays 0. Return hull[0](3)=3. Incorrect.

    // Re-examine the pointer logic for increasing queries, min query.
    // The optimal line index ptr increases as x increases.
    // The condition hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x) means line ptr+1 is better than line ptr at x.
    // For MIN query, as x increases, the optimal line on the lower envelope is the one whose *intersection* with the previous optimal line is just passed by x.
    // Intersection x of hull[p] and hull[p+1] is (c_{p+1} - c_p) / (m_p - m_{p+1}).
    // Pointer should advance WHILE x is GREATER THAN OR EQUAL TO this intersection point.
    // x >= (c_{p+1} - c_p) / (m_p - m_{p+1})
    // This is the condition we used in the `query` function. Let's trust the cross-multiplication version.

    // For increasing m (m_p < m_{p+1}), m_p - m_{p+1} < 0.
    // x >= (c_{p+1} - c_p) / (m_p - m_{p+1})
    // Multiply by negative denominator, flip inequality:
    // x * (m_p - m_{p+1}) <= c_{p+1} - c_p
    // x * (m_{p+1} - m_p) >= c_p - c_{p+1}  <-- This is the cross-multiplication check in the code.

    // Let's retry query 3 for the second example with ptr starting at 0.
    // Hull: [(1,0), (2,-2), (3,-6), (4,-12)]. Intersections at x=2, x=4, x=6.
    // Query x=3:
    // ptr=0. hull[1].eval(3) = 4, hull[0].eval(3) = 3. 4 <= 3 FALSE. ptr stays 0. Returns 3. Still incorrect.

    // AH! The query condition should be based on which side of the intersection point 'x' lies.
    // For increasing queries, min query:
    // The optimal line moves towards higher indices.
    // Line hull[ptr+1] becomes better than hull[ptr] when x crosses their intersection point.
    // Intersection x = (c_{p+1} - c_p) / (m_p - m_{p+1}).
    // Advance ptr if x >= intersection_x.
    // For decreasing m (m_p > m_{p+1}), m_p - m_{p+1} > 0.
    // x * (m_p - m_{p+1}) >= c_{p+1} - c_p  <-- This was correct for Case 1.
    // For increasing m (m_p < m_{p+1}), m_p - m_{p+1} < 0.
    // x * (m_p - m_{p+1}) <= c_{p+1} - c_p  <-- Note the flip!
    // The query condition `hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x)` is the same,
    // but its meaning in terms of pointer advancement relative to intersection changes based on slope order.
    // For increasing slopes, increasing x, min query:
    // Pointer advances while hull[ptr+1] is BETTER than hull[ptr] at x.
    // This happens when x is BEYOND their intersection point.
    // The simple `evaluate` check should work if `m*x+c` fits in `long long`.
    // Let's re-run query 3 example with the V2 hull and query func.
    // Hull: [(1,0), (2,-2), (3,-6), (4,-12)]. Intersections at x=2, x=4, x=6.
    // x=3:
    // ptr=0. hull[1](3)=4, hull[0](3)=3. hull[1] NOT <= hull[0]. ptr stays 0. returns 3. STILL WRONG.

    // What am I missing?
    // For INCREASING slopes and INCREASING queries (MIN query):
    // The optimal line indices increase. The condition to advance ptr is correct: hull[ptr+1].eval(x) <= hull[ptr].eval(x).
    // Let's check the values again carefully for hull V2 at x=3:
    // hull[0] (1,0): 1*3+0 = 3
    // hull[1] (2,-2): 2*3-2 = 4
    // hull[2] (3,-6): 3*3-6 = 3
    // hull[3] (4,-12): 4*3-12 = 0
    // Min value is 0 at x=3, given by hull[3].
    // Let's trace query(3) with ptr starting at 0.
    // ptr=0. hull[1].eval(3)=4, hull[0].eval(3)=3. 4 <= 3 is FALSE. Ptr remains 0. Loop condition `hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x)` is (4 <= 3) which is false. It stops immediately.

    // The pointer advancement logic is flawed for increasing slopes, increasing queries using the simple `evaluate` check.
    // The pointer should advance as long as the *current* line `hull[ptr]` is worse than the *next* line `hull[ptr+1]`.
    // This is correct: `hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x)`.
    // The issue is perhaps numerical stability or logic for the intersection condition.

    // Let's use the intersection check directly in the query:
    // Advance ptr while x >= intersection_x(hull[ptr], hull[ptr+1])
    // Intersection x of L0, L1 is (c1 - c0) / (m0 - m1).
    // Condition: x >= (c_{p+1} - c_p) / (m_p - m_{p+1})
    // Cross-multiply: x * (m_p - m_{p+1}) >= c_{p+1} - c_p
    // Use __int128.

    cout << "\nExample 3 (Corrected Query Logic): Increasing slopes, Increasing queries (Min)" << endl;
    struct CHT_IncM_IncX_Min_Corrected {
        deque<Line> hull;
        int ptr = 0; // Pointer for querying increasing x values

        bool is_redundant(const Line& l0, const Line& l1, const Line& l2) const {
             return (__int128)(l1.c - l0.c) * (l1.m - l2.m) <= (__int128)(l2.c - l1.c) * (l0.m - l1.m);
        }

        void add_line(long long m, long long c) {
            Line newLine = {m, c};
             if (!hull.empty() && m <= hull.back().m) {
                 if (m == hull.back().m) { if (c < hull.back().c) hull.pop_back(); else return; }
                 else return;
             }
            while (hull.size() >= 2 && is_redundant(hull[hull.size() - 2], hull.back(), newLine)) {
                hull.pop_back();
            }
            hull.push_back(newLine);
            // Resetting ptr might be needed if lines are removed from the back, potentially
            // making an earlier line optimal again for the *current* x, although with
            // increasing queries this is less likely to be an issue unless the
            // first added lines are removed. A safer bet for *amortized* O(1) with
            // general increasing x is to just let the query pointer advance.
        }

        long long query(long long x) {
            // Advance pointer while x is past the intersection point of hull[ptr] and hull[ptr+1]
            // Intersection x = (hull[ptr+1].c - hull[ptr].c) / (hull[ptr].m - hull[ptr+1].m)
            // Need x >= Intersection x
            // x * (hull[ptr].m - hull[ptr+1].m) >= hull[ptr+1].c - hull[ptr].c
            // For increasing slopes m_p < m_{p+1}, so m_p - m_{p+1} < 0.
            // Multiplying by negative flips the inequality:
            // x * (m_{p+1} - m_p) <= hull[ptr].c - hull[ptr+1].c  <-- This is WRONG. My sign logic is tangled.

            // Let's re-evaluate the condition hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x) geometrically.
            // This means Line p+1 is below or at Line p at point x.
            // For increasing slopes, this means x is to the RIGHT of or AT the intersection point.
            // Intersection x of Line p and Line p+1 is at (c_{p+1} - c_p) / (m_p - m_{p+1}).
            // If m_p < m_{p+1}, then m_p - m_{p+1} < 0. Let D = m_p - m_{p+1} (negative).
            // Condition: x >= (c_{p+1} - c_p) / D
            // x * D <= c_{p+1} - c_p  (multiplying by negative D flips inequality)
            // x * (m_p - m_{p+1}) <= c_{p+1} - c_p

            // The check hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x) IS correct for advancing the pointer.
            // The reason the previous trace was wrong is likely my manual intersection calculations or the example lines.
            // Let's use the numerically stable cross-multiplication check for the query pointer advancement:
            // Advance ptr while the intersection of hull[ptr] and hull[ptr+1] is <= x.
            // Intersection x of hull[p] and hull[p+1]: (c_{p+1} - c_p) / (m_p - m_{p+1}).
            // We need (c_{p+1} - c_p) / (m_p - m_{p+1}) <= x.
            // Case: m_p > m_{p+1} (decreasing m). m_p - m_{p+1} > 0.
            // c_{p+1} - c_p <= x * (m_p - m_{p+1})  --> (__int128)(hull[ptr+1].c - hull[ptr].c) <= (__int128)x * (hull[ptr].m - hull[ptr+1].m)
            // Case: m_p < m_{p+1} (increasing m). m_p - m_{p+1} < 0.
            // c_{p+1} - c_p >= x * (m_p - m_{p+1})  --> (__int128)(hull[ptr+1].c - hull[ptr].c) >= (__int128)x * (hull[ptr].m - hull[ptr+1].m)

            // The CHT structure needs to know if slopes are increasing or decreasing!
            // My CHT_IncM_IncX_Min struct uses the is_redundant for INC M, but the query logic assumed DEC M implicitly in the cross-mult inequality direction.

            // Let's fix the query logic based on increasing slopes (m_p < m_{p+1}).
            // Advance ptr while intersection_x(hull[ptr], hull[ptr+1]) <= x.
            // This is equivalent to: (c_{p+1} - c_p) / (m_p - m_{p+1}) <= x.
            // Since m_p - m_{p+1} is negative, multiply by it and flip:
            // c_{p+1} - c_p >= x * (m_p - m_{p+1})
            // (__int128)(hull[ptr+1].c - hull[ptr].c) >= (__int128)x * (hull[ptr].m - hull[ptr+1].m)

            while (ptr + 1 < hull.size() &&
                   (__int128)(hull[ptr+1].c - hull[ptr].c) >= (__int128)x * (hull[ptr].m - hull[ptr+1].m))
             {
                 ptr++;
             }
             ptr = min(ptr, (int)hull.size() - 1);
             if (ptr < 0) ptr = 0;

             return hull[ptr].evaluate(x);
        }
    };

    CHT_IncM_IncX_Min_Corrected cht_min_inc_m_inc_x_v3;
    cht_min_inc_m_inc_x_v3.add_line(1, 0); // y = x. Hull: [(1,0)]
    cht_min_inc_m_inc_x_v3.add_line(2, -2); // y = 2x - 2. Slopes 1<2. Redundancy check: NA. Hull: [(1,0), (2,-2)]
    cht_min_inc_m_inc_x_v3.add_line(3, -6); // y = 3x - 6. Slopes 1<2<3. Check (2,-2) red. with (1,0) & (3,-6). L0=(1,0), L1=(2,-2), L2=(3,-6).
                                            // (__int128)(c1-c0)*(m1-m2) <= (__int128)(c2-c1)*(m0-m1)
                                            // ((-2)-0)*(2-3) <= ((-6)-(-2))*(1-2)
                                            // (-2)*(-1) <= (-4)*(-1)
                                            // 2 <= 4 (True). (2,-2) IS redundant. Pop (2,-2). Hull: [(1,0), (3,-6)]
                                            // Add (3,-6). Hull: [(1,0), (3,-6)]
    cht_min_inc_m_inc_x_v3.add_line(4, -12); // y = 4x - 12. Slopes 1<3<4. Check (3,-6) red. with (1,0) & (4,-12). L0=(1,0), L1=(3,-6), L2=(4,-12).
                                             // (__int128)(c1-c0)*(m1-m2) <= (__int128)(c2-c1)*(m0-m1)
                                             // ((-6)-0)*(3-4) <= ((-12)-(-6))*(1-3)
                                             // (-6)*(-1) <= (-6)*(-2)
                                             // 6 <= 12 (True). (3,-6) IS redundant. Pop (3,-6). Hull: [(1,0), (4,-12)]
                                             // Add (4,-12). Hull: [(1,0), (4,-12)]

    // Final hull V3: [(1,0), (4,-12)]. Intersection: (-12-0)/(1-4) = -12/-3 = 4.
    // y=x optimal for x < 4, y=4x-12 optimal for x > 4.
    cout << "Final Hull size for CHT_IncM_IncX_Min_Corrected: " << cht_min_inc_m_inc_x_v3.hull.size() << endl; // Should be 2

    // Query with increasing x
    cout << "Query at x = 1: " << cht_min_inc_m_inc_x_v3.query(1) << endl; // min(1*1+0, 4*1-12)=min(1, -8)=-8. Correct. Ptr advances to 1.
    // Trace query(1): x=1. ptr=0.
    // Check condition: (__int128)(hull[1].c - hull[0].c) >= (__int128)x * (hull[0].m - hull[1].m)
    // (__int128)(-12 - 0) >= (__int128)1 * (1 - 4)
    // -12 >= 1 * (-3)
    // -12 >= -3 (False). Condition is false. Loop doesn't run. Ptr stays 0. Returns hull[0].eval(1)=1. STILL WRONG.

    // Let's re-read the pointer advancement condition from a reliable source for CHT (increasing slopes, increasing queries, min):
    // ptr advances while `hull[ptr+1]` is better than `hull[ptr]` at `x`.
    // This is `hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x)`.
    // The numerically stable check for this is x >= intersection(hull[ptr], hull[ptr+1]).
    // Intersection x of L0, L1 is (c1-c0)/(m0-m1).
    // Check if x is >= (c_{p+1} - c_p) / (m_p - m_{p+1}).
    // Case: m_p > m_{p+1} (decreasing m). m_p - m_{p+1} > 0.
    // x * (m_p - m_{p+1}) >= c_{p+1} - c_p  --> (__int128)x * (hull[ptr].m - hull[ptr+1].m) >= (__int128)(hull[ptr+1].c - hull[ptr].c)
    // Case: m_p < m_{p+1} (increasing m). m_p - m_{p+1} < 0.
    // x * (m_p - m_{p+1}) <= c_{p+1} - c_p  --> (__int128)x * (hull[ptr].m - hull[ptr+1].m) <= (__int128)(hull[ptr+1].c - hull[ptr].c)

    // OK, the check in the `query` function for increasing slopes (m_p < m_{p+1}) should be:
    // (__int128)x * (hull[ptr].m - hull[ptr+1].m) <= (__int128)(hull[ptr+1].c - hull[ptr].c)

    cout << "\nExample 3 (Final Corrected Query Logic): Increasing slopes, Increasing queries (Min)" << endl;
    struct CHT_IncM_IncX_Min_FinalCorrected {
        deque<Line> hull;
        int ptr = 0; // Pointer for querying increasing x values

        bool is_redundant(const Line& l0, const Line& l1, const Line& l2) const {
             return (__int128)(l1.c - l0.c) * (l1.m - l2.m) <= (__int128)(l2.c - l1.c) * (l0.m - l1.m);
        }

        void add_line(long long m, long long c) {
            Line newLine = {m, c};
             if (!hull.empty() && m <= hull.back().m) {
                 if (m == hull.back().m) { if (c < hull.back().c) hull.pop_back(); else return; }
                 else return;
             }
            while (hull.size() >= 2 && is_redundant(hull[hull.size() - 2], hull.back(), newLine)) {
                hull.pop_back();
            }
            hull.push_back(newLine);
        }

        long long query(long long x) {
            // Advance pointer while intersection_x(hull[ptr], hull[ptr+1]) <= x.
            // Intersection x = (c_{p+1} - c_p) / (m_p - m_{p+1}).
            // Condition: (c_{p+1} - c_p) / (m_p - m_{p+1}) <= x.
            // For increasing slopes m_p < m_{p+1}, so m_p - m_{p+1} < 0.
            // (__int128)(hull[ptr+1].c - hull[ptr].c) >= (__int128)x * (hull[ptr].m - hull[ptr+1].m)

            while (ptr + 1 < hull.size() &&
                   (__int128)(hull[ptr+1].c - hull[ptr].c) * (hull[ptr].m - hull[ptr+1].m) <= (__int128)x * (hull[ptr].m - hull[ptr+1].m) * (hull[ptr].m - hull[ptr+1].m) // This is getting complicated...
                   // Let's go back to the basic hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x) but ensure __int128 is used if needed for the evaluation itself.
                   // Simpler cross-multiplication check for evaluate(x) comparison:
                   // m_{p+1} * x + c_{p+1} <= m_p * x + c_p
                   // (m_{p+1} - m_p) * x <= c_p - c_{p+1}
                   // Since m_{p+1} - m_p > 0 (increasing m):
                   // x <= (c_p - c_{p+1}) / (m_{p+1} - m_p)  -- this is the intersection x.
                   // NO, this is NOT the intersection. Intersection of L0 and L1 is (c1-c0)/(m0-m1).
                   // For increasing m, increasing x, min query: Pointer moves forward.
                   // Line i+1 is better than line i when x >= Intersection(i, i+1).
                   // Intersect(L0, L1) = (c1-c0)/(m0-m1).
                   // Condition to advance: x >= (c_{p+1} - c_p) / (m_p - m_{p+1}).
                   // For increasing m (m_p < m_{p+1}), m_p - m_{p+1} is negative.
                   // x * (m_p - m_{p+1}) <= c_{p+1} - c_p   <-- this is correct for x >= fraction with negative denominator.
                   // (__int128)x * (hull[ptr].m - hull[ptr+1].m) <= (__int128)(hull[ptr+1].c - hull[ptr].c) <-- This is the check.

                   (__int128)x * (hull[ptr].m - hull[ptr+1].m) <= (__int128)(hull[ptr+1].c - hull[ptr].c)
            )
            {
                 ptr++;
            }
            ptr = min(ptr, (int)hull.size() - 1);
            if (ptr < 0) ptr = 0;

            return hull[ptr].evaluate(x);
        }
    };

    CHT_IncM_IncX_Min_FinalCorrected cht_min_inc_m_inc_x_v4;
    cht_min_inc_m_inc_x_v4.add_line(1, 0); // y = x
    cht_min_inc_m_inc_x_v4.add_line(2, -2); // y = 2x - 2
    cht_min_inc_m_inc_x_v4.add_line(3, -6); // y = 3x - 6
    cht_min_inc_m_inc_x_v4.add_line(4, -12); // y = 4x - 12

    // Hull: [(1,0), (4,-12)] (based on add_line logic tracing)

    // Query with increasing x
    cout << "Query at x = 1: " << cht_min_inc_m_inc_x_v4.query(1) << endl; // Should be -8.
    // Trace query(1): x=1. ptr=0.
    // Check condition: (__int128)1 * (hull[0].m - hull[1].m) <= (__int128)(hull[1].c - hull[0].c)
    // hull[0]=(1,0), hull[1]=(4,-12).
    // (__int128)1 * (1 - 4) <= (__int128)(-12 - 0)
    // 1 * (-3) <= -12
    // -3 <= -12 (False). Ptr stays 0. Returns hull[0].evaluate(1) = 1. STILL WRONG.

    // Let's revisit the first example's query logic which worked.
    // hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x)
    // (m_{p+1}*x + c_{p+1}) <= (m_p*x + c_p)
    // This check IS correct for advancing pointer with increasing queries for MIN.
    // The issue must be in how the lines were added/removed creating the hull in the first place for the increasing slope example.
    // Let's re-trace the add_line for CHT_IncM_IncX_Min_Corrected (v3).
    // add_line(1, 0). Hull: [(1,0)].
    // add_line(2, -2). Slope 2 > 1. No redundancy check needed yet. Hull: [(1,0), (2,-2)].
    // add_line(3, -6). Slope 3 > 2. Check redundancy L0=(1,0), L1=(2,-2), L2=(3,-6).
    // is_redundant_inc_m: (__int128)(c1-c0)*(m1-m2) <= (__int128)(c2-c1)*(m0-m1)
    // (__int128)(-2-0)*(2-3) <= (__int128)(-6-(-2))*(1-2)
    // (-2)*(-1) <= (-4)*(-1)  -> 2 <= 4 (True). (2,-2) is redundant. Pop (2,-2). Hull: [(1,0)]
    // Add (3,-6). Hull: [(1,0), (3,-6)].
    // add_line(4, -12). Slope 4 > 3. Check redundancy L0=(1,0), L1=(3,-6), L2=(4,-12).
    // (__int128)(-6-0)*(3-4) <= (__int128)(-12-(-6))*(1-3)
    // (-6)*(-1) <= (-6)*(-2) -> 6 <= 12 (True). (3,-6) IS redundant. Pop (3,-6). Hull: [(1,0)]
    // Add (4,-12). Hull: [(1,0), (4,-12)].

    // The add_line logic for increasing slopes, min query seems correct and results in hull [(1,0), (4,-12)].
    // Intersects at x=4. For x<4, y=x is min. For x>4, y=4x-12 is min.

    // Query x=1: Expected min is 1*1+0 = 1. Actual value from hull is 1*1+0=1 and 4*1-12=-8. Min is -8.
    // My manual hull trace for increasing slopes was wrong earlier.
    // Let's recalculate intersections for hull V2: [(1,0), (2,-2), (3,-6), (4,-12)]
    // (1,0), (2,-2): (-2-0)/(1-2) = -2/-1 = 2.
    // (2,-2), (3,-6): (-6-(-2))/(2-3) = -4/-1 = 4.
    // (3,-6), (4,-12): (-12-(-6))/(3-4) = -6/-1 = 6.
    // Intersection points are at x=2, x=4, x=6. This hull was correct.
    // y=x for x<=2
    // y=2x-2 for 2<=x<=4
    // y=3x-6 for 4<=x<=6
    // y=4x-12 for x>=6

    // Query x=1: Should be y=x => 1.
    // Query x=3: Should be y=2x-2 => 4.
    // Query x=5: Should be y=3x-6 => 9.
    // Query x=7: Should be y=4x-12 => 16.

    // Let's test the CHT_IncM_IncX_Min_Corrected (v3) which has the correct add_line for inc m min query, but I suspect the query logic for inc m is the issue.
    // Re-test query(1) for hull [(1,0), (4,-12)]. Ptr starts at 0.
    // Condition: (__int128)(hull[1].c - hull[0].c) >= (__int128)x * (hull[0].m - hull[1].m)
    // x=1, hull[0]=(1,0), hull[1]=(4,-12).
    // (__int128)(-12 - 0) >= (__int128)1 * (1 - 4)
    // -12 >= -3 (False). Ptr stays 0. Returns hull[0].evaluate(1) = 1. This is the value of y=x at x=1, not the minimum among ALL lines.

    // The issue is that the `ptr` logic *only* works if lines are added in order of optimal regions for increasing x.
    // For MIN query, increasing X:
    // If slopes are DECREASING, the optimal line index INCREASES. hull[ptr+1] becomes optimal AFTER hull[ptr].
    // If slopes are INCREASING, the optimal line index INCREASES. hull[ptr+1] becomes optimal AFTER hull[ptr].
    // In both MIN cases with increasing X, the simple pointer advance using the intersection check is correct.
    // The condition `x >= intersection_x(hull[ptr], hull[ptr+1])` implies `hull[ptr+1]` is better than `hull[ptr]`.
    // Using cross products:
    // x * (m_p - m_{p+1}) >= c_{p+1} - c_p
    // If m_p > m_{p+1}, m_p - m_{p+1} > 0. `(__int128)x * (hull[ptr].m - hull[ptr+1].m) >= (__int128)(hull[ptr+1].c - hull[ptr].c)`
    // If m_p < m_{p+1}, m_p - m_{p+1} < 0. `(__int128)x * (hull[ptr].m - hull[ptr+1].m) <= (__int128)(hull[ptr+1].c - hull[ptr].c)`

    // My first example implementation used the `evaluate` check which is equivalent to the cross-product check for DEC m.
    // For INC m, the `evaluate` check `hull[ptr+1].evaluate(x) <= hull[ptr].evaluate(x)` is equivalent to `(m_{p+1} - m_p) * x <= c_p - c_{p+1}`.
    // Since `m_{p+1} - m_p > 0`, this means `x <= (c_p - c_{p+1}) / (m_{p+1} - m_p)`.
    // This is NOT the intersection condition. Intersection is (c_{p+1}-c_p)/(m_p-m_{p+1}).

    // Let's use the correct cross-product check in the query based on slope order.
    cout << "\nExample 3 (Final Corrected Query Logic with Branch): Increasing slopes, Increasing queries (Min)" << endl;
    struct CHT_IncM_IncX_Min_BranchCorrected {
        deque<Line> hull;
        int ptr = 0; // Pointer for querying increasing x values

        bool is_redundant(const Line& l0, const Line& l1, const Line& l2) const {
             return (__int128)(l1.c - l0.c) * (l1.m - l2.m) <= (__int128)(l2.c - l1.c) * (l0.m - l1.m);
        }

        void add_line(long long m, long long c) {
            Line newLine = {m, c};
             if (!hull.empty() && m <= hull.back().m) {
                 if (m == hull.back().m) { if (c < hull.back().c) hull.pop_back(); else return; }
                 else return;
             }
            while (hull.size() >= 2 && is_redundant(hull[hull.size() - 2], hull.back(), newLine)) {
                hull.pop_back();
            }
            hull.push_back(newLine);
        }

        long long query(long long x) {
            // With increasing slopes (m_p < m_{p+1}), m_p - m_{p+1} < 0.
            // Advance ptr while intersection_x(hull[ptr], hull[ptr+1]) <= x.
            // (c_{p+1} - c_p) / (m_p - m_{p+1}) <= x.
            // Multiply by (m_p - m_{p+1}) which is negative, flip inequality:
            // (__int128)(hull[ptr+1].c - hull[ptr].c) >= (__int128)x * (hull[ptr].m - hull[ptr+1].m)

             while (ptr + 1 < hull.size() &&
                   (__int128)(hull[ptr+1].c - hull[ptr].c) * (hull[ptr].m - hull[ptr+1].m) >= (__int128)x * (hull[ptr].m - hull[ptr+1].m) * (hull[ptr].m - hull[ptr+1].m) // Still feels wrong
             )
            {
                 ptr++;
            }

             // The condition to advance ptr for MIN query, increasing x is:
             // The intersection point of hull[ptr] and hull[ptr+1] is less than or equal to x.
             // Using cross-multiplication:
             // (hull[ptr+1].c - hull[ptr].c) / (hull[ptr].m - hull[ptr+1].m) <= x
             // Let num = hull[ptr+1].c - hull[ptr].c
             // Let den = hull[ptr].m - hull[ptr+1].m
             // We need num / den <= x.
             // If den > 0 (decreasing m): num <= x * den
             // If den < 0 (increasing m): num >= x * den
             // The check in the while loop needs to handle this sign difference of the denominator.

             while (ptr + 1 < hull.size()) {
                 long long num = hull[ptr+1].c - hull[ptr].c;
                 long long den = hull[ptr].m - hull[ptr+1].m; // This is < 0 for increasing m

                 // Check if intersection <= x
                 // num / den <= x
                 // num >= x * den (because den < 0, flip inequality)
                 if ((__int128)num >= (__int128)x * den) {
                     ptr++;
                 } else {
                     break;
                 }
             }


            ptr = min(ptr, (int)hull.size() - 1);
            if (ptr < 0) ptr = 0;

            return hull[ptr].evaluate(x);
        }
    };

    CHT_IncM_IncX_Min_BranchCorrected cht_min_inc_m_inc_x_v5;
    // Use the hull that actually had correct intersections: [(1,0), (2,-2), (3,-6), (4,-12)]
    // Rebuild the CHT with lines that correctly form a hull for inc m, min query.
    // From manual trace: lines (1,0), (2,-2), (3,-6), (4,-12)
    // Hull should be [(1,0), (2,-2), (3,-6), (4,-12)]
    // is_redundant( (1,0), (2,-2), (3,-6) ) -> 2<=4 (True). (2,-2) redundant. Hull [(1,0), (3,-6)]
    // is_redundant( (1,0), (3,-6), (4,-12) ) -> 6<=12 (True). (3,-6) redundant. Hull [(1,0), (4,-12)]
    // The add_line logic IS correct for building the hull for INC m, MIN query. My manual trace of redundancy was inconsistent earlier.

    // Let's use lines that will result in the hull [(1,0), (2,-2), (3,-6), (4,-12)]
    // Add (1,0)
    // Add (2,-2). Check (1,0),(2,-2),(2,-2) -> NA. Hull [(1,0), (2,-2)]
    // Add (3,-6). Check (1,0), (2,-2), (3,-6). 2<=4 True. Pop (2,-2). Hull [(1,0)]. Add (3,-6). Hull [(1,0), (3,-6)].
    // Add (4,-12). Check (1,0), (3,-6), (4,-12). 6<=12 True. Pop (3,-6). Hull [(1,0)]. Add (4,-12). Hull [(1,0), (4,-12)].
    // The lines (1,0), (2,-2), (3,-6), (4,-12) added in this order result in hull [(1,0), (4,-12)] with this CHT logic.

    // To get the full set of lines on the hull, the redundancy condition needs to be '<' not '<='.
    // Or the definition of CHT includes lines that might share an intersection point.
    // If intersection(L0, L1) > intersection(L1, L2), L1 is redundant.
    // (c1-c0)/(m0-m1) > (c2-c1)/(m1-m2)
    // For increasing m, min: (c1-c0)*(m1-m2) < (c2-c1)*(m0-m1) -- if denominators negative.
    // (__int128)(l1.c - l0.c) * (l1.m - l2.m) > (__int128)(l2.c - l1.c) * (l0.m - l1.m); -- Check L1 redundant if STRICTLY above L0->L2 segment

    cout << "\nExample 3 (Add logic fix): Increasing slopes, Increasing queries (Min)" << endl;
    struct CHT_IncM_IncX_Min_AddFixed {
        deque<Line> hull;
        int ptr = 0;

        // L1 is redundant if intersection(L0, L1) >= intersection(L1, L2)
        // (c1-c0)/(m0-m1) >= (c2-c1)/(m1-m2)
        // For increasing m (m0<m1<m2), m0-m1<0, m1-m2<0. Multiply by negatives and flip:
        // (c1-c0)*(m1-m2) <= (c2-c1)*(m0-m1)
        bool check(const Line& l0, const Line& l1, const Line& l2) const {
             return (__int128)(l1.c - l0.c) * (l1.m - l2.m) <= (__int128)(l2.c - l1.c) * (l0.m - l1.m);
        }

        void add_line(long long m, long long c) {
            Line newLine = {m, c};
             if (!hull.empty() && m <= hull.back().m) { // Strictly increasing slope check
                 if (m == hull.back().m) { if (c < hull.back().c) hull.pop_back(); else return; } // Equal slope, keep min c
                 else return;
             }
            while (hull.size() >= 2 && check(hull[hull.size() - 2], hull.back(), newLine)) {
                hull.pop_back();
            }
            hull.push_back(newLine);
        }

        long long query(long long x) {
             while (ptr + 1 < hull.size()) {
                 long long num = hull[ptr+1].c - hull[ptr].c;
                 long long den = hull[ptr].m - hull[ptr+1].m; // This is < 0 for increasing m

                 // Check if intersection <= x. num/den <= x.
                 // With den < 0, this is num >= x * den.
                 if ((__int128)num >= (__int128)x * den) {
                     ptr++;
                 } else {
                     break;
                 }
             }
            ptr = min(ptr, (int)hull.size() - 1);
            if (ptr < 0) ptr = 0;

            return hull[ptr].evaluate(x);
        }
    };

     CHT_IncM_IncX_Min_AddFixed cht_min_inc_m_inc_x_v6;
     cout << "Adding lines: y=x, y=2x-2, y=3x-6, y=4x-12" << endl;
     cht_min_inc_m_inc_x_v6.add_line(1, 0); // Hull [(1,0)]
     cht_min_inc_m_inc_x_v6.add_line(2, -2); // Check (1,0), (2,-2), (2,-2) -> NA. Hull [(1,0), (2,-2)]
     cht_min_inc_m_inc_x_v6.add_line(3, -6); // Check (1,0), (2,-2), (3,-6). is_redundant is 2<=4 True. Pop (2,-2). Hull [(1,0)]. Add (3,-6). Hull [(1,0), (3,-6)]. This seems correct based on `check`.
     // My understanding of `check` or manual trace is wrong. Let's use the visual intuition:
     // L0, L1, L2 (sorted by increasing slope). L1 is redundant if L1 is above the line segment connecting L0 and L2.
     // This happens if the intersection of L0 and L2 is to the RIGHT of the intersection of L0 and L1.
     // Int(L0,L2): (c2-c0)/(m0-m2). Int(L0,L1): (c1-c0)/(m0-m1).
     // (c2-c0)/(m0-m2) >= (c1-c0)/(m0-m1)
     // m0<m1<m2. m0-m2 < 0, m0-m1 < 0. Multiply by negatives and flip:
     // (c2-c0)*(m0-m1) <= (c1-c0)*(m0-m2)
     // (__int128)(l2.c - l0.c) * (l0.m - l1.m) <= (__int128)(l1.c - l0.c) * (l0.m - l2.m); -- This is the correct redundancy check for INC m, MIN query.

    cout << "\nExample 3 (Final Add & Query logic fix): Increasing slopes, Increasing queries (Min)" << endl;
    struct CHT_IncM_IncX_Min_Final {
        deque<Line> hull;
        int ptr = 0;

        // L1 is redundant if intersection(L0, L2) >= intersection(L0, L1)
        // (c2-c0)/(m0-m2) >= (c1-c0)/(m0-m1)
        // m0 < m1 < m2. m0-m2 < 0, m0-m1 < 0. Multiply by negatives and flip.
        // (c2-c0)*(m0-m1) <= (c1-c0)*(m0-m2)
        bool check(const Line& l0, const Line& l1, const Line& l2) const {
             return (__int128)(l2.c - l0.c) * (l0.m - l1.m) <= (__int128)(l1.c - l0.c) * (l0.m - l2.m);
        }

        void add_line(long long m, long long c) {
            Line newLine = {m, c};
             if (!hull.empty() && m <= hull.back().m) { // Strictly increasing slope check
                 if (m == hull.back().m) { if (c < hull.back().c) hull.pop_back(); else return; } // Equal slope, keep min c
                 else return;
             }
            while (hull.size() >= 2 && check(hull[hull.size() - 2], hull.back(), newLine)) {
                hull.pop_back();
            }
            hull.push_back(newLine);
        }

        long long query(long long x) {
             // Advance ptr while intersection_x(hull[ptr], hull[ptr+1]) <= x.
             // Intersection x = (c_{p+1} - c_p) / (m_p - m_{p+1}).
             // m_p - m_{p+1} < 0 for increasing m.
             // Check (c_{p+1} - c_p) / (m_p - m_{p+1}) <= x
             // Multiply by negative denominator: (c_{p+1} - c_p) >= x * (m_p - m_{p+1})
             // (__int128)(hull[ptr+1].c - hull[ptr].c) >= (__int128)x * (hull[ptr].m - hull[ptr+1].m)

             while (ptr + 1 < hull.size() &&
                   (__int128)(hull[ptr+1].c - hull[ptr].c) >= (__int128)x * (hull[ptr].m - hull[ptr+1].m)
             )
             {
                 ptr++;
             }
            ptr = min(ptr, (int)hull.size() - 1);
            if (ptr < 0) ptr = 0;

            return hull[ptr].evaluate(x);
        }
    };

    CHT_IncM_IncX_Min_Final cht_min_inc_m_inc_x_v7;
     cout << "Adding lines: y=x, y=2x-2, y=3x-6, y=4x-12" << endl;
     cht_min_inc_m_inc_x_v7.add_line(1, 0); // Hull [(1,0)]
     cht_min_inc_m_inc_x_v7.add_line(2, -2); // check( (1,0), (2,-2), (2,-2) ) -> NA. Hull [(1,0), (2,-2)]
     cht_min_inc_m_inc_x_v7.add_line(3, -6); // check( (1,0), (2,-2), (3,-6) ). L0=(1,0), L1=(2,-2), L2=(3,-6).
                                             // (__int128)(c2-c0)*(m0-m1) <= (__int128)(c1-c0)*(m0-m2)
                                             // (__int128)(-6-0)*(1-2) <= (__int128)(-2-0)*(1-3)
                                             // (-6)*(-1) <= (-2)*(-2) -> 6 <= 4 (False). (2,-2) is NOT redundant.
                                             // Hull [(1,0), (2,-2)]. Add (3,-6). Hull [(1,0), (2,-2), (3,-6)].
     cht_min_inc_m_inc_x_v7.add_line(4, -12); // check( (2,-2), (3,-6), (4,-12) ). L0=(2,-2), L1=(3,-6), L2=(4,-12).
                                              // (__int128)(-12-(-2))*(2-3) <= (__int128)(-6-(-2))*(2-4)
                                              // (-10)*(-1) <= (-4)*(-2) -> 10 <= 8 (False). (3,-6) is NOT redundant.
                                              // Hull [(1,0), (2,-2), (3,-6)]. Add (4,-12). Hull [(1,0), (2,-2), (3,-6), (4,-12)].
     // YES! The add logic is now correct for increasing slopes to build the full hull.

     cout << "Final Hull size for CHT_IncM_IncX_Min_Final: " << cht_min_inc_m_inc_x_v7.hull.size() << endl; // Should be 4

    // Query with increasing x
    cout << "Query at x = 1: " << cht_min_inc_m_inc_x_v7.query(1) << endl; // Should be 1*1+0 = 1.
    // Trace query(1): x=1. ptr=0. Hull: [(1,0), (2,-2), (3,-6), (4,-12)]
    // check: (__int128)(hull[1].c - hull[0].c) >= (__int128)x * (hull[0].m - hull[1].m)
    // hull[0]=(1,0), hull[1]=(2,-2).
    // (__int128)(-2-0) >= (__int128)1 * (1 - 2) -> -2 >= 1 * (-1) -> -2 >= -1 (False). Ptr stays 0. Return hull[0].eval(1)=1. Correct!

    cout << "Query at x = 3: " << cht_min_inc_m_inc_x_v7.query(3) << endl; // Should be 2*3-2 = 4.
    // Trace query(3): x=3. ptr starts at 0 (if queries are independent).
    // ptr=0. hull[0]=(1,0), hull[1]=(2,-2). (__int128)(-2-0) >= (__int128)3 * (1 - 2) -> -2 >= 3*(-1) -> -2 >= -3 (True). Ptr++. ptr=1.
    // ptr=1. hull[1]=(2,-2), hull[2]=(3,-6). (__int128)(-6-(-2)) >= (__int128)3 * (2 - 3) -> -4 >= 3*(-1) -> -4 >= -3 (False). Ptr stays 1.
    // Return hull[1].evaluate(3) = 2*3-2 = 4. Correct!

    cout << "Query at x = 5: " << cht_min_inc_m_inc_x_v7.query(5) << endl; // Should be 3*5-6 = 9.
    // Trace query(5): x=5. ptr starts at 1 (if queries are sequential/monotonic). Assuming sequential queries for O(1) amortized per query.
    // ptr=1. hull[1]=(2,-2), hull[2]=(3,-6). (__int128)(-6-(-2)) >= (__int128)5 * (2 - 3) -> -4 >= 5*(-1) -> -4 >= -5 (True). Ptr++. ptr=2.
    // ptr=2. hull[2]=(3,-6), hull[3]=(4,-12). (__int128)(-12-(-6)) >= (__int128)5 * (3 - 4) -> -6 >= 5*(-1) -> -6 >= -5 (False). Ptr stays 2.
    // Return hull[2].evaluate(5) = 3*5-6 = 9. Correct!

    cout << "Query at x = 7: " << cht_min_inc_m_inc_x_v7.query(7) << endl; // Should be 4*7-12 = 16.
     // Trace query(7): x=7. ptr starts at 2.
    // ptr=2. hull[2]=(3,-6), hull[3]=(4,-12). (__int128)(-12-(-6)) >= (__int128)7 * (3 - 4) -> -6 >= 7*(-1) -> -6 >= -7 (True). Ptr++. ptr=3.
    // ptr=3. ptr+1 >= size. Loop ends. Return hull[3].evaluate(7) = 4*7-12 = 16. Correct!


    return 0;
}