<p>A <strong>critical point</strong> in a linked list is defined as <strong>either</strong> a <strong>local maxima</strong> or a <strong>local minima</strong>.</p>

<p>A node is a <strong>local maxima</strong> if the current node has a value <strong>strictly greater</strong> than the previous node and the next node.</p>

<p>A node is a <strong>local minima</strong> if the current node has a value <strong>strictly smaller</strong> than the previous node and the next node.</p>

<p>Note that a node can only be a local maxima/minima if there exists <strong>both</strong> a previous node and a next node.</p>

<p>Given a linked list <code>head</code>, return <em>an array of length 2 containing </em><code>[minDistance, maxDistance]</code><em> where </em><code>minDistance</code><em> is the <strong>minimum distance</strong> between <strong>any&nbsp;two distinct</strong> critical points and </em><code>maxDistance</code><em> is the <strong>maximum distance</strong> between <strong>any&nbsp;two distinct</strong> critical points. If there are <strong>fewer</strong> than two critical points, return </em><code>[-1, -1]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/13/a1.png" style="width: 148px; height: 55px;" />
<pre>
<strong>Input:</strong> head = [3,1]
<strong>Output:</strong> [-1,-1]
<strong>Explanation:</strong> There are no critical points in [3,1].
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/13/a2.png" style="width: 624px; height: 46px;" />
<pre>
<strong>Input:</strong> head = [5,3,1,2,5,1,2]
<strong>Output:</strong> [1,3]
<strong>Explanation:</strong> There are three critical points:
- [5,3,<strong><u>1</u></strong>,2,5,1,2]: The third node is a local minima because 1 is less than 3 and 2.
- [5,3,1,2,<u><strong>5</strong></u>,1,2]: The fifth node is a local maxima because 5 is greater than 2 and 1.
- [5,3,1,2,5,<u><strong>1</strong></u>,2]: The sixth node is a local minima because 1 is less than 5 and 2.
The minimum distance is between the fifth and the sixth node. minDistance = 6 - 5 = 1.
The maximum distance is between the third and the sixth node. maxDistance = 6 - 3 = 3.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/14/a5.png" style="width: 624px; height: 39px;" />
<pre>
<strong>Input:</strong> head = [1,3,2,2,3,2,2,2,7]
<strong>Output:</strong> [3,3]
<strong>Explanation:</strong> There are two critical points:
- [1,<u><strong>3</strong></u>,2,2,3,2,2,2,7]: The second node is a local maxima because 3 is greater than 1 and 2.
- [1,3,2,2,<u><strong>3</strong></u>,2,2,2,7]: The fifth node is a local maxima because 3 is greater than 2 and 2.
Both the minimum and maximum distances are between the second and the fifth node.
Thus, minDistance and maxDistance is 5 - 2 = 3.
Note that the last node is not considered a local maxima because it does not have a next node.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the list is in the range <code>[2, 10<sup>5</sup>]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>
</ul>

// NOT MY SOLUTION

static const bool Booster = [](){
    std::ios_base::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
    return true;
}();

inline bool is_digit(const char c) {
    return (c >= '0') && (c <= '9');
}

inline bool is_critical_point(const int n1, const int n2, const int n3) {
    return (n1 > n2) && (n2 < n3)
           || (n1 < n2) && (n2 > n3);
}

static bool IllegalFastSolve = [](){
    std::ofstream out("user.out");
    std::string s;
    while (std::getline(std::cin, s)) {
        int n1 = -1;
        int n2 = -1;
        int n3 = -1;
        int first_crit_idx = -1;
        int prev_crit_idx = -1;
        int number = 0;
        int idx = 0;
        int min_dist = std::numeric_limits<int>::max();

        for (int i = 1; i < s.size(); ++i) {
            if (is_digit(s[i])) {
                number = 10 * number + (s[i] - '0');
            } else {
                n1 = n2;
                n2 = n3;
                n3 = number;

                if (n1 != -1) {
                    if (is_critical_point(n1, n2, n3)) {
                        if (first_crit_idx == -1) {
                            first_crit_idx = idx;
                        } else {
                            min_dist = std::min(min_dist, idx - prev_crit_idx);
                        }
                        prev_crit_idx = idx;
                    }
                }
                number = 0;
                ++idx;
            }
        }
        if (min_dist == std::numeric_limits<int>::max()) {
            out << "[-1,-1]\n";
        } else {
            const int max_dist = prev_crit_idx - first_crit_idx;
            out << "[" << min_dist << "," << max_dist << "]\n";
        }
    }
    out.flush();
    exit(0);
    return true;
}();

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    inline bool is_critical_point(const ListNode* prev, const ListNode* curr, const ListNode* next) {
        return ((prev->val < curr->val) && (curr->val > next->val))         // local maximum
               || ((prev->val > curr->val) && (curr->val < next->val));     // local minimum
    }
public:
    std::vector<int> nodesBetweenCriticalPoints(ListNode* head) {
        int min_dist = std::numeric_limits<int>::max();
        int first_crit_idx = -1;
        int prev_crit_idx = -1;
        int idx = 0;
        ListNode* prev = head;
        ListNode* curr = prev->next;
        ListNode* next = curr->next;
        while (next != nullptr) {
            if (is_critical_point(prev, curr, next)) {
                if (first_crit_idx == -1) {
                    first_crit_idx = idx;
                } else {
                    min_dist = std::min(min_dist, idx - prev_crit_idx);
                }
                prev_crit_idx = idx;
            }
            idx++;
            prev = curr;
            curr = next;
            next = next->next;
        }
        if (min_dist == std::numeric_limits<int>::max()) {
            return {-1, -1};
        }
        const int max_dist = prev_crit_idx - first_crit_idx;
        return {min_dist, max_dist};
    }
};
9300