// — Arithmetic —
max(3, 7);                                 // 7
min(3, 7);                                 // 3
max({1, 5, 3, 7, 2});                      // 7   (initializer_list, C++11)
abs(-5);                                   // 5
fabs(-3.14);                               // 3.14

// — Power & Root —
pow(2, 10);                                // 1024.0 (double)
(int)pow(2, 10);                           // 1024   (safe for small values)
(long long)pow(10, 18);                    // may lose precision!
sqrt(49.0);                                // 7.0
(int)sqrt(49);                             // 7

// Perfect square check
int sq = (int)sqrt(n);
bool ok = sq * sq == n || (sq + 1) * (sq + 1) == n;

// — Rounding —
floor(2.7);                                // 2.0
ceil(2.1);                                 // 3.0
round(2.5);                                // 3.0

// — Logarithms —
log(exp(1));                               // 1.0 (natural log)
log2(8);                                   // 3.0
log10(1000);                               // 3.0

// Number of digits in n (n must be > 0; log10(0) is -inf!)
int digits = (int)log10(n) + 1;           // 9999 → 4

// — Ceiling division (positive a, b only) —
int cdiv = (a + b - 1) / b;              // ceil(a / b) without float

// — Safe infinity for DP / shortest path —
const int INF = 1e9;                      // 1e9 + 1e9 = 2e9, fits in int
const int INF2 = INT_MAX / 2;            // safe for a single addition
const long long LINF = 1000000000000000000LL; // for long long problems

// — Negative modulo —
// C++ % keeps sign of dividend: -7 % 3 == -1 (not 2!)
int mod = ((a % n) + n) % n;             // always-positive modulo

// GCD — C++17 (or use __gcd on GCC)
#include <numeric>
gcd(12, 8);                                // 4
lcm(4, 6);                                // 12

// GCD — Euclidean algorithm O(log min(a,b))
int gcd(int a, int b) {
    while (b) { a %= b; swap(a, b); }
    return a;
}

// LCM — divide first to avoid overflow
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

// isPrime — trial division O(√n)
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; (long long)i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

// Modular exponentiation O(log exp)
const int MOD = 1'000'000'007;

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1; base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

// Safe modular add (cast to long long to avoid overflow)
((long long)(a % MOD) + (b % MOD)) % MOD;

// Safe modular multiply (use long long)
(1LL * a * b) % MOD;

// 1D DP with infinity
vector<int> dp(n, 1e9);
dp[0] = 0;  // base case

// 2D DP with infinity
vector<vector<int>> dp(m, vector<int>(n, 1e9));

// memset trick: 0 and -1 only (sets each byte)
int dp[N];
memset(dp, 0, sizeof dp);               // all zeros
memset(dp, -1, sizeof dp);              // all -1 (0xFF bytes = -1 in two's complement)
memset(dp, 0x3f, sizeof dp);            // ~1e9 per cell (0x3f3f3f3f)

// Boolean DP
vector<bool> dp(n + 1, false);
dp[0] = true;  // base: empty subset

// Space-optimized (two variables) — House Robber pattern
int prev2 = 0, prev1 = 0;
for (int num : nums) {
    int curr = max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = curr;
}

// ❌ Signed overflow is UB — compiler may optimize away checks!
int a = INT_MAX;
int b = a + 1;      // UB! not guaranteed to wrap

// The compiler can assume signed overflow never happens,
// and may REMOVE your overflow guard:
if (a + 1 > a) { }  // compiler may optimize to always-true

// ✅ Cast to long long before arithmetic
long long safe = (long long)a + 1;

// ✅ Or check before adding
if (a > INT_MAX - b) { /* would overflow */ }

// ❌ Two ints multiplied — result overflows before assignment
int w = 50000, h = 50000;
long long area = w * h;     // UB! overflow happens in int

// ✅ Cast at least one operand to long long
long long area = 1LL * w * h;
long long area = (long long)w * h;

// ❌ Overflows when lo + hi > INT_MAX
int mid = (lo + hi) / 2;

// ✅ Safe midpoint
int mid = lo + (hi - lo) / 2;

// C++ has no >>> — use the subtraction form above
// For unsigned: (lo + hi) / 2 is safe

// ❌ -INT_MIN overflows (no positive counterpart in 32-bit)
abs(INT_MIN);              // UB!
int n = INT_MIN;
int neg = -n;              // UB!

// ✅ Cast to long long first
abs((long long)INT_MIN);   // 2147483648LL

// ✅ Guard in abs helper
long long safeAbs(int n) {
    return abs((long long)n);
}

// ❌ INT_MAX + w is UB
int INF = INT_MAX;
if (dist[u] + w < dist[v]) { ... }  // UB when dist[u]=INF

// ✅ Use 1e9 as INF (1e9 + 1e9 = 2e9, fits in int)
const int INF = 1e9;

// ✅ Or guard before adding
if (dist[u] != INF && dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
}

// — int ↔ string —
string s = to_string(42);                 // "42"
string s = to_string(-3.14);              // "-3.140000"

int n = stoi("42");                        // 42
long long n = stoll("123456789012");       // 123456789012LL
double d = stod("3.14");                   // 3.14

// stoi with base
stoi("1010", nullptr, 2);                  // 10 (binary)
stoi("FF", nullptr, 16);                   // 255 (hex)

// — char ↔ int index —
int idx = 'c' - 'a';                      // 2
int d   = '7' - '0';                      // 7
char ch = 'a' + 2;                        // 'c'
int code = (int)'A';                      // 65

// — stringstream (flexible parsing) —
#include <sstream>
stringstream ss("10 20 30");
int a, b, c;
ss >> a >> b >> c;                       // 10, 20, 30

// Build string from parts
ostringstream oss;
oss << "val=" << 42;
string result = oss.str();                // "val=42"

// — Radix conversions —
bitset<8>(10).to_string();                // "00001010" (binary)
// Hex output via printf or stringstream
char buf[16];
sprintf(buf, "%x", 255);                 // "ff"

// ❌ stoi throws std::invalid_argument on non-numeric input
stoi("abc");                               // throws!

// ❌ stoi throws std::out_of_range if value exceeds int
stoi("99999999999");                       // throws!

// ✅ Wrap in try-catch if input is untrusted
try {
    int n = stoi(s);
} catch (const exception& e) {
    // handle error
}

// For competitive programming, input is typically well-formed
// — stoi/stoll is safe without try-catch

isdigit(c);                     // '0'..'9'
isalpha(c);                     // a-z, A-Z
isalnum(c);                     // letter or digit
isspace(c);                     // space, tab, newline
isupper(c);                     // A-Z
islower(c);                     // a-z

// Fast inline ASCII checks (tight loops):
c >= 'a' && c <= 'z';          // lowercase
c >= 'A' && c <= 'Z';          // uppercase
c >= '0' && c <= '9';          // digit

toupper('a');                   // 'A' (returns int, cast to char)
tolower('A');                   // 'a'

// Bit-level case tricks (ASCII letters only):
c | ' ';    // force lowercase  ('A'→'a', 'a'→'a')
c & '_';    // force uppercase  ('a'→'A', 'A'→'A')
c ^ ' ';    // toggle case      ('a'↔'A')
// ' ' = 32 = 0b0010_0000,  '_' = 95 = 0b0101_1111

// Vowel check
char lower = tolower(c);
bool isVowel = lower=='a' || lower=='e' || lower=='i'
            || lower=='o' || lower=='u';

// — Single-bit operations —
(n >> i) & 1;                             // check bit i
n |= 1 << i;                             // set bit i
n &= ~(1 << i);                          // clear bit i
n ^= 1 << i;                             // toggle bit i

// — Lowest set bit, Kernighan's —
// Use unsigned to avoid UB when n == INT_MIN: (unsigned)n & -(unsigned)n
n & (-n);                                 // isolate rightmost 1: 12(1100) → 4(0100)
n &= n - 1;                              // clear lowest set bit

// Count set bits — Kernighan's O(k)
int count = 0;
for (int x = n; x; x &= x - 1) count++;

// Count set bits — built-in O(1)
__builtin_popcount(n);                    // int
__builtin_popcountll(n);                  // long long

// — Shifts, even/odd —
n << k;    // n × 2^k
n >> k;    // n ÷ 2^k (arithmetic for signed, usually)
n & 1;     // 0 = even, 1 = odd

// — XOR rules —
a ^ 0 == a;        // unchanged
a ^ a == 0;        // self-cancels ← key for Single Number
a ^ b ^ a == b;    // associative + self-cancel

// — Swap without temp —
swap(a, b);        // std::swap (preferred)
a ^= b; b ^= a; a ^= b;  // XOR trick (avoid — less readable)

// — Negate via bits (two's complement) —
~n + 1;             // same as -n

// — Update bit i to value v (0 or 1) —
n = (n & ~(1 << i)) | (v << i);

// — Highest one bit (floor power of 2, n must be > 0) —
// __builtin_clz(0) is UB — always guard n > 0
1 << (31 - __builtin_clz(n));            // 12 → 8, 16 → 16

// — Bitmask & subset enumeration —
(1 << n) - 1;       // n=4 → 0b1111 = 15

for (int sub = m; sub > 0; sub = (sub - 1) & m) {
    // process sub
}
// don't forget empty subset (sub = 0)

// ❌ Shifting 1 (int) by 31+ bits is UB
int mask = 1 << 31;         // UB! 1 is signed int

// ✅ Use 1LL for shifts ≥ 31
long long mask = 1LL << 40;

// ✅ Or use unsigned
unsigned mask = 1u << 31;   // OK, unsigned

// ❌ 0 falsely passes
return (n & (n - 1)) == 0;

// ✅ Must check n > 0
return n > 0 && (n & (n - 1)) == 0;

// Empty vector
vector<int> v;                            // size=0, capacity=0

// Pre-sized (n elements, all zeros)
vector<int> v(n);                         // [0, 0, ..., 0]
vector<int> v(n, val);                    // [val, val, ..., val]

// Initializer list
vector<int> v = {1, 2, 3};
vector<int> v{1, 2, 3};                  // same

// From range
vector<int> v(arr, arr + n);             // from C-array
vector<int> v(other.begin(), other.end());

// Pre-allocate capacity (size stays 0)
vector<int> v;
v.reserve(1000);                          // no reallocation until size > 1000

// 2D vector
vector<vector<int>> grid(rows, vector<int>(cols, 0));

// 2D vector (jagged)
vector<vector<int>> adj(n);              // adjacency list

// — Sort —
sort(v.begin(), v.end());                  // ascending
sort(v.begin(), v.end(), greater<int>());  // descending
sort(v.rbegin(), v.rend());                // also descending

// Sort 2D by first element
sort(intervals.begin(), intervals.end());  // lexicographic by default

// — Copy —
vector<int> cp = v;                        // deep copy (value semantics)

// 2D clone
vector<vector<int>> cp2d = grid;          // deep copy (each inner vector copied)

// — Aggregate —
int sum = accumulate(v.begin(), v.end(), 0);
long long sum = accumulate(v.begin(), v.end(), 0LL);  // avoid int overflow
int mn = *min_element(v.begin(), v.end());
int mx = *max_element(v.begin(), v.end());

// — Reverse in-place —
reverse(v.begin(), v.end());

// — Shuffle —
mt19937 rng(42);
shuffle(v.begin(), v.end(), rng);

// — Remove at index i —
v.erase(v.begin() + i);                   // O(n), order preserved
swap(v[i], v.back()); v.pop_back();        // O(1), order lost

// — Rotate left by k —
rotate(v.begin(), v.begin() + k, v.end());

// — Remove duplicates (sorted) —
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

// — Erase-remove idiom —
v.erase(remove(v.begin(), v.end(), val), v.end());

// — Print —
for (int x : v) cout << x << " ";        // 1 2 3

// ❌ v.size() returns size_t (unsigned)
// On empty vector: v.size() - 1 = 18446744073709551615!
vector<int> v;
for (int i = 0; i < v.size() - 1; i++) { }  // huge loop!

// ✅ Cast to int, or guard with empty check
for (int i = 0; i < (int)v.size() - 1; i++) { }
if (!v.empty()) { /* safe to use v.size() - 1 */ }

// ❌ push_back may reallocate, invalidating all iterators
vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4);           // may reallocate!
*it;                       // UB — dangling iterator

// ✅ Re-obtain iterators after modification
v.push_back(4);
it = v.begin();            // safe now

// ✅ Or reserve to prevent reallocation
v.reserve(100);
auto it = v.begin();
v.push_back(4);            // no realloc if size <= 100
*it;                        // safe

// — Access —
s.size();                       // length (same as s.length())
s[i];                           // char at index i
s.front();                      // first char
s.back();                       // last char
s.substr(i, len);               // substring [i, i+len)
s.substr(i);                    // from i to end

// — Search —
s.find("sub");                  // first occurrence, string::npos if not found
s.rfind("sub");                 // last occurrence
s.find('x');                    // first char occurrence
s.find("sub", pos);            // search starting at pos

// — Modify in-place —
s[i] = 'x';                    // direct char assignment
s += "world";                   // append
s.push_back('!');               // append char
s.pop_back();                   // remove last char
s.insert(5, " ");              // insert at position
s.erase(3, 2);                 // erase 2 chars at position 3

// — Transform —
// To lowercase (in-place) — cast to unsigned char for safety with non-ASCII
transform(s.begin(), s.end(), s.begin(),
    [](unsigned char c){ return tolower(c); });
// To uppercase (in-place)
transform(s.begin(), s.end(), s.begin(),
    [](unsigned char c){ return toupper(c); });

// Reverse (in-place)
reverse(s.begin(), s.end());

// — Split by delimiter —
stringstream ss(s);
string token;
vector<string> parts;
while (getline(ss, token, ',')) parts.push_back(token);

// Split by whitespace
istringstream iss(s);
string word;
while (iss >> word) parts.push_back(word);

// — Join —
// No built-in join; use a loop with ostringstream
ostringstream oss;
for (int i = 0; i < v.size(); i++) {
    if (i) oss << ",";
    oss << v[i];
}
string joined = oss.str();

// — Comparison & anagram key —
s1 == s2;                       // value comparison ✅
s1 < s2;                       // lexicographic

// Sorted key for anagram grouping
string key = s;
sort(key.begin(), key.end());

// Frequency array key (no sort needed, assumes lowercase a-z only)
int freq[26] = {};
for (char c : s) freq[c - 'a']++;

// — Repeat a string —
string(5, 'a');                 // "aaaaa"
// For repeating a string: use a loop or accumulate

// ❌ Comparing find result with -1 or 0
if (s.find("sub") == -1) { }   // works by accident but fragile
if (s.find("sub")) { }         // WRONG — 0 means "found at index 0"

// ✅ Always compare with string::npos
if (s.find("sub") != string::npos) {
    // found
}

// npos = (size_t)-1 = 18446744073709551615

// Empty string → palindrome (true)
// Single char → palindrome (true)

// Valid Palindrome: strip non-alphanumeric, lowercase
bool isPalindrome(string s) {
    string clean;
    for (char c : s)
        if (isalnum(c)) clean += tolower(c);
    string rev = clean;
    reverse(rev.begin(), rev.end());
    return clean == rev;
}

// Two-pointer version (O(1) space):
int l = 0, r = s.size() - 1;
while (l < r) {
    while (l < r && !isalnum(s[l])) l++;
    while (l < r && !isalnum(s[r])) r--;
    if (tolower(s[l]) != tolower(s[r])) return false;
    l++; r--;
}
return true;

// Sort ascending
sort(v.begin(), v.end());

// Sort descending
sort(v.begin(), v.end(), greater<int>());
sort(v.rbegin(), v.rend());

// Custom comparator (lambda)
sort(v.begin(), v.end(), [](int a, int b) {
    return a < b;                          // ascending
});

// Stable sort (preserves equal-element order)
stable_sort(v.begin(), v.end());

// Sort intervals by start asc, end desc (tie-break)
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
    if (a[0] != b[0]) return a[0] < b[0];
    return a[1] > b[1];
});

// Sort by string length
sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
    return a.size() < b.size();
});

// Largest Number #179 — concat comparison
sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
    return a + b > b + a;
});

// Sort by absolute value (cast to long long to avoid abs(INT_MIN) UB)
sort(v.begin(), v.end(), [](int a, int b) {
    return abs((long long)a) < abs((long long)b);
});

// Check if sorted
is_sorted(v.begin(), v.end());

// Partial sort: k smallest elements in first k positions
partial_sort(v.begin(), v.begin() + k, v.end());

// nth_element: O(n) — puts nth element in sorted position
nth_element(v.begin(), v.begin() + k, v.end());
// v[k] is now the (k+1)th smallest; elements before it are ≤, after are ≥

// Next permutation
next_permutation(v.begin(), v.end());  // returns false if already last

// ❌ Using <= violates strict weak ordering — UB!
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;   // WRONG — equal elements must return false
});
// May crash, infinite loop, or corrupt memory

// ✅ Use < (strict less-than)
sort(v.begin(), v.end(), [](int a, int b) {
    return a < b;
});

// Lower/upper bound (sorted vector)
auto lb = lower_bound(v.begin(), v.end(), target);  // first ≥ target
auto ub = upper_bound(v.begin(), v.end(), target);  // first > target
int idx = lb - v.begin();                            // convert to index

bool found = binary_search(v.begin(), v.end(), target);

// Count occurrences in sorted range
auto [lo, hi] = equal_range(v.begin(), v.end(), target);
int cnt = hi - lo;

// Find minimum in rotated sorted array (= pivot index)
int findMin(vector<int>& nums) {
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// Search in rotated array
int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid])
                hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi])
                lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

// ❌ No progress when lo=0, hi=1: mid=0, lo stays 0
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (valid(mid)) hi = mid;
    else lo = mid;  // ← INFINITE LOOP!
}

// ✅ Always advance by at least 1
lo = mid + 1;

// Rule: lo < hi  → boundary-finding
// Rule: lo <= hi → exact-match

// First occurrence: use lower_bound
auto it = lower_bound(v.begin(), v.end(), target);
int first = (it != v.end() && *it == target) ? it - v.begin() : -1;

// Last occurrence: use upper_bound - 1
auto it = upper_bound(v.begin(), v.end(), target);
int last = (it != v.begin() && *(it-1) == target) ? (it-1) - v.begin() : -1;

// Or manual binary search — keep searching when found:
if (nums[mid] == target) hi = mid;       // first: search LEFT
if (nums[mid] == target) lo = mid + 1;   // last: search RIGHT

// lo/hi must cover the complete valid range!

// Koko Eating Bananas:
lo = 1;                            // minimum possible rate
hi = *max_element(p.begin(), p.end()); // one pile per hour

// Capacity to Ship:
lo = *max_element(w.begin(), w.end());  // must fit heaviest
hi = accumulate(w.begin(), w.end(), 0); // everything in one day

// isFeasible must be monotone!

// — unordered_map (hash map) —
unordered_map<int, int> m;
m[key] = val;                        // insert or update
m[key];                              // access (inserts 0 if missing!)
m.count(key);                        // 0 or 1 (existence check)
auto it = m.find(key);               // iterator, m.end() if not found
if (it != m.end()) use(it->second);
m.erase(key);                        // remove
m.size();                            // count

// Frequency counting
unordered_map<int, int> freq;
for (int n : nums) freq[n]++;

// Decrement and remove if zero
freq[key]--;
if (freq[key] == 0) freq.erase(key);

// Group by key
unordered_map<int, vector<int>> groups;
groups[key].push_back(val);          // auto-inits vector

// — unordered_set (hash set) —
unordered_set<int> s;
s.insert(val);                       // add
s.count(val);                        // 0 or 1
s.erase(val);                        // remove
s.size();

// Set from vector
unordered_set<int> s(v.begin(), v.end());

// — map (ordered, red-black tree) —
map<int, int> om;
om.begin()->first;                   // smallest key
om.rbegin()->first;                  // largest key
auto lb = om.lower_bound(k);        // first key ≥ k
auto ub = om.upper_bound(k);        // first key > k

// — set (ordered) —
set<int> os;
os.insert(val);
auto it = os.lower_bound(val);      // first ≥ val

// — multiset (allows duplicates) —
multiset<int> ms;
ms.insert(5); ms.insert(5);
ms.count(5);                        // 2
ms.erase(ms.find(5));               // remove ONE occurrence
ms.erase(5);                        // remove ALL occurrences

// Iterate ordered map
for (auto& [k, v] : om) { /* sorted by key */ }

// Check if two maps have same keys and values
m1 == m2;                            // ✅ works for map and unordered_map

// ❌ m[key] inserts a default-constructed value if key is absent
unordered_map<int, int> m;
if (m[5] == 0) { }                   // now m contains {5: 0}!
m.size();                            // 1 — unintended insertion

// ✅ Use count() or find() for existence checks
if (m.count(5)) { }                  // no side effect
if (m.find(5) != m.end()) { }       // no side effect

// Adversarial input can force hash collisions → O(n) per op
// This happens in competitive programming with anti-hash tests

// ✅ Use a custom hash to defend against it
struct custom_hash {
    size_t operator()(size_t x) const {
        x ^= x >> 16;
        x *= 0x45d9f3b;
        x ^= x >> 16;
        return x;
    }
};
unordered_map<int, int, custom_hash> m;

// ✅ Or just use map (O(log n) guaranteed) if TLE suspected

multiset<int> ms = {3, 3, 3, 5};

// ❌ erase(value) removes ALL occurrences
ms.erase(3);                         // removes all 3s! ms = {5}

// ✅ erase(iterator) removes exactly one — check find() != end() first!
auto it = ms.find(3);
if (it != ms.end()) ms.erase(it);   // removes one 3, ms = {3, 3, 5}

// Max-heap (default)
priority_queue<int> maxPQ;
maxPQ.push(5); maxPQ.push(3);
maxPQ.top();                               // 5 (largest)

// Min-heap
priority_queue<int, vector<int>, greater<int>> minPQ;
minPQ.push(5); minPQ.push(3);
minPQ.top();                               // 3 (smallest)

// Pair-based min-heap for {distance, node} — Dijkstra
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.push({0, src});
auto [d, u] = pq.top(); pq.pop();

// Custom comparator via lambda (C++20 or function object)
auto cmp = [](const auto& a, const auto& b) {
    return a.freq < b.freq;                // max-heap by freq
};
priority_queue<Item, vector<Item>, decltype(cmp)> pq(cmp);

// Custom comparator via struct
struct Cmp {
    bool operator()(const pair<int,int>& a, const pair<int,int>& b) {
        if (a.first != b.first) return a.first < b.first;  // max by first
        return a.second > b.second;                         // min by second
    }
};
priority_queue<pair<int,int>, vector<pair<int,int>>, Cmp> pq;

// Top-K via min-heap (partial sort)
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : data) {
    pq.push(x);
    if ((int)pq.size() > k) pq.pop();    // evict smallest
}
// pq now holds the k largest elements

// ❌ Forgetting that default is max-heap (opposite of Java!)
priority_queue<int> pq;
pq.push(3); pq.push(1); pq.push(5);
pq.top();                              // 5, NOT 1!

// In Java: PriorityQueue is min-heap by default
// In C++: priority_queue is MAX-heap by default

// ✅ For min-heap, specify greater<>
priority_queue<int, vector<int>, greater<int>> pq;

// — Stack —
stack<int> st;
st.push(x);                               // push
st.top();                                  // peek
st.pop();                                  // pop (returns void!)
st.empty();                                // isEmpty

// — Queue —
queue<int> q;
q.push(x);                                // enqueue
q.front();                                 // peek front
q.back();                                  // peek back
q.pop();                                   // dequeue (returns void!)

// — Deque —
deque<int> dq;
dq.push_back(x);                          // push to back
dq.push_front(x);                         // push to front
dq.pop_back();                            // pop from back
dq.pop_front();                           // pop from front
dq.front();                               // peek front
dq.back();                                // peek back
dq[i];                                    // random access O(1)

// — Sliding window maximum (monotonic decreasing deque) —
deque<int> dq;  // stores indices
for (int i = 0; i < (int)nums.size(); i++) {
    while (!dq.empty() && nums[dq.back()] < nums[i])
        dq.pop_back();                     // remove smaller from back
    dq.push_back(i);
    if (dq.front() <= i - k) dq.pop_front(); // out of window
    if (i >= k - 1)
        result.push_back(nums[dq.front()]);
}

// ❌ pop() does NOT return the element (unlike Java/Go/Python)
stack<int> st;
st.push(5);
int val = st.pop();            // compile error! pop() returns void

// ✅ Read first, then pop
int val = st.top();
st.pop();

// Same for queue: read front() first, then pop()
int val = q.front();
q.pop();

// ❌ UB: no exception, may crash or return garbage
stack<int> st;
st.top();                      // UB!
st.pop();                      // UB!

// ✅ Always check before accessing
if (!st.empty()) { int val = st.top(); st.pop(); }
if (!q.empty()) { int val = q.front(); q.pop(); }

// Monotonic stack: after loop, remaining elements have
// no "next greater" → result stays default (often 0 or -1)

// Largest Rectangle (#84): append sentinel height 0
// to force all bars to pop at the end
heights.push_back(0);

// Next Greater Element: remaining stack elements → result = -1
// (already handled if result initialized to -1)

// 4-directional (up, right, down, left)
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};

// 8-directional (includes diagonals)
int dr8[] = {-1,-1,-1, 0, 0, 1, 1, 1};
int dc8[] = {-1, 0, 1,-1, 1,-1, 0, 1};

// Bounds check
auto inBounds = [&](int r, int c) {
    return r >= 0 && r < rows && c >= 0 && c < cols;
};

for (int d = 0; d < 4; d++) {
    int nr = r + dr[d], nc = c + dc[d];
    if (inBounds(nr, nc)) { /* valid neighbor */ }
}

// 2D ↔ 1D index
int idx = r * cols + c;
int r2 = idx / cols, c2 = idx % cols;

// Transpose (square matrix)
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        swap(mat[i][j], mat[j][i]);
// Rotate 90° clockwise (square matrix) = transpose + reverse each row

// Spiral traversal: 4 boundaries shrinking
int top = 0, bot = m - 1, left = 0, right = n - 1;
while (top <= bot && left <= right) {
    // → top row, ↓ right col, ← bottom row, ↑ left col
    top++; right--; bot--; left++;
}

// Diagonal properties:
// Same diagonal:      r - c  is constant
// Same anti-diagonal: r + c  is constant

// Grid DFS (4-directional)
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int r, int c) {
    if (r < 0 || r >= (int)grid.size() || c < 0 || c >= (int)grid[0].size()
        || vis[r][c]) return;
    vis[r][c] = true;
    for (int d = 0; d < 4; d++)
        dfs(grid, vis, r + dr[d], c + dc[d]);
}

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

struct TrieNode {
    TrieNode* children[26] = {};
    bool isEnd = false;
};

// Adjacency list — unweighted undirected
vector<vector<int>> adj(n);
for (auto& e : edges) {
    adj[e[0]].push_back(e[1]);
    adj[e[1]].push_back(e[0]);    // omit for directed
}

// Weighted: pair<int,int>{neighbor, weight}
vector<vector<pair<int,int>>> adj(n);
adj[u].push_back({v, w});

// In-degree array (for Kahn's topo sort)
vector<int> inDeg(n, 0);
for (auto& e : edges) inDeg[e[1]]++;

// Union-Find (DSU) with path compression + union by rank
vector<int> parent(n), rank_(n, 0);
iota(parent.begin(), parent.end(), 0);    // parent[i] = i

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

bool unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return false;
    if (rank_[px] < rank_[py]) swap(px, py);
    parent[py] = px;
    if (rank_[px] == rank_[py]) rank_[px]++;
    return true;
}

if (!head) return nullptr;
if (!head->next) return head;

// Iterate safely
while (curr) curr = curr->next;

// Dummy head avoids nullptr checks for head insertion/deletion
ListNode dummy(0);
dummy.next = head;
// ... work with dummy ...
return dummy.next;

// ✅ Short-circuit: fast checked before fast->next
while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
}

// ✅ Reverse: save next before overwriting
ListNode* next = curr->next;    // 1. save
curr->next = prev;              // 2. reverse
prev = curr;                    // 3. advance prev
curr = next;                    // 4. advance curr

// Floyd's cycle: phase 2 — find cycle start (after phase 1 meets at slow)
auto ptr = head;
while (ptr != slow) {
    ptr = ptr->next; slow = slow->next;
}
return ptr;  // cycle entry point

// DFS base case — always first line
if (!node) return 0;

// BFS start
if (!root) return result;

// ❌ BST validate with int bounds fails for INT_MIN node
// ✅ Always use long long bounds
bool validate(TreeNode* n, long long lo, long long hi) {
    if (!n) return true;
    if (n->val <= lo || n->val >= hi) return false;
    return validate(n->left, lo, n->val)
        && validate(n->right, n->val, hi);
}
validate(root, LLONG_MIN, LLONG_MAX);

// Max Path Sum: init to INT_MIN (not 0!)
int ans = INT_MIN;
int leftGain = max(0, maxGain(n->left));
int rightGain = max(0, maxGain(n->right));

// Skewed tree (n=10^5 all left): use iterative traversal
stack<TreeNode*> st;
auto curr = root;
while (curr || !st.empty()) {
    while (curr) { st.push(curr); curr = curr->left; }
    curr = st.top(); st.pop();
    curr = curr->right;
}

// ❌ Only visits component containing node 0
dfs(graph, 0, visited);
// ✅ Start from every unvisited node
for (int i = 0; i < n; i++)
    if (!visited[i]) { dfs(graph, i, visited); components++; }

// Dijkstra: must skip stale entries
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;

// Dijkstra: unreachable nodes
if (dist[dst] == INF) return -1;
// ❌ Dijkstra with negative weights → use Bellman-Ford

// Undirected DFS: ignore parent, not all visited neighbors
if (neighbor == parent) continue;
if (visited[neighbor]) return true;      // real cycle
// For directed: use 3-state (unvisited / in-stack / done)

// Standard algorithm handles p-is-ancestor correctly
TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    auto left = lca(root->left, p, q);
    auto right = lca(root->right, p, q);
    if (left && right) return root;
    return left ? left : right;
}

// — String palindrome (two pointers) —
int l = 0, r = s.size() - 1;
while (l < r) {
    if (s[l] != s[r]) return false;
    l++; r--;
}

// — Integer palindrome (no string conversion) —
if (x < 0 || (x % 10 == 0 && x != 0)) return false;
int rev = 0;
while (x > rev) { rev = rev * 10 + x % 10; x /= 10; }
return x == rev || x == rev / 10;

// — Expand around center (longest palindrome) —
int expand(const string& s, int l, int r) {
    while (l >= 0 && r < (int)s.size() && s[l] == s[r]) { l--; r++; }
    return r - l - 1;
}

// — Find minimum / maximum —
int ans = INT_MAX;
ans = min(ans, candidate);

// — Collect results: always snapshot the vector! —
result.push_back(current);                // ✅ vector has value semantics
// (unlike Go/Java where slices/lists are references)

// — Frequency arrays —
int freq[26] = {};                        // 26 lowercase letters
for (char c : s) freq[c - 'a']++;
int freq128[128] = {};                    // 128 ASCII

// — Early-return checklist —
if (nums.empty())   return ...;           // array
if (s.empty())      return ...;           // string
if (!root)          return ...;           // tree
if (!head)          return head;          // linked list
if (k > (int)nums.size()) return 0;      // window too large

if (k > (int)nums.size()) return 0;
if (p.size() > s.size()) return false;    // Permutation In String

// Matches counter — increment only at exact boundary
if (window[c] == need[c]) formed++;

// Decrement only when crossing below threshold
window[lc]--;
if (window[lc] < need[lc]) formed--;

// Min Window Substring: no valid window → return ""
string result = "";
if (minLen > (int)s.size()) return "";

// Max Consecutive Ones: all ones → return n
// All zeros → return 0 (default)

// Longest Substring w/o Repeat:
//   all unique → return n
//   all same char → return 1

// Climbing Stairs: n=1 → dp[i-2] accesses dp[-1]
if (n <= 1) return n;

// Decode Ways: s[0]='0' → 0 ways immediately
// Coin Change: amount=0 → 0 (no coins needed)
// Edit Distance: dp[i][0]=i, dp[0][j]=j → don't forget!

// House Robber II: can't use first and last together
if (nums.size() == 1) return nums[0];     // guard before split
int r1 = rob(nums, 0, n - 2);
int r2 = rob(nums, 1, n - 1);
return max(r1, r2);

// Unbounded (Coin Change): each coin reusable → loop FORWARD
for (int coin : coins)
    for (int j = coin; j <= amount; j++)
        dp[j] = min(dp[j], dp[j - coin] + 1);

// 0/1 Knapsack: each item once → loop BACKWARD
for (auto& item : items)
    for (int j = W; j >= item.w; j--)
        dp[j] = max(dp[j], dp[j - item.w] + item.v);

// C++ vectors have value semantics — push_back copies automatically
result.push_back(curr);           // ✅ safe, deep copy

// ❌ i > 0: skips valid combinations (too aggressive)
if (i > 0 && nums[i] == nums[i-1]) continue;
// ✅ i > start: only skip duplicates at same recursion level
if (i > start && nums[i] == nums[i-1]) continue;
// MUST sort array first!
sort(nums.begin(), nums.end());

// Kadane's: ❌ init maxSoFar = 0 → [-3,-1,-2] wrongly returns 0
// ✅ Init from first element
int maxSoFar = nums[0], curr = nums[0];

// Max Product [2,3,0,4]: zero resets the subarray
// Product Except Self with zero: 2+ zeros → all products are zero

// 3Sum [0,0,0] → skip: if (i > 0 && nums[i] == nums[i-1]) continue;

// Longest Consecutive [1,1,1] → answer=1 (not 3); use set

// Rotated Sorted Array II [1,1,1,1]: can't determine sorted half
if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {
    lo++; hi--;  // linear fallback
}

// Subarray length: right - left + 1
// Substring s.substr(i, len): starts at i, length len

// for (l < r) vs for (l <= r)
// Binary search: lo <= hi for exact-match
// Binary search: lo < hi  for boundary-finding

// Return conventions:
// Binary Search not found    → -1
// Coin Change impossible     → -1 (NOT 0!)
// Min Window no window       → ""
// Subsets: empty set {}      → valid result

// Integer comparison: no autoboxing pitfall in C++
int a = 1000, b = 1000;
a == b;   // ✅ true (C++ has no Integer cache issue)

// ✅ Guard before any logic
if (nums.empty()) return ...;
if ((int)nums.size() < 2) return nums[0];

// Kadane's: init with nums[0], loop from i=1 → needs guard
// Two pointers: right = nums.size()-1 → wraps if empty (size_t!)
// Fixed window: k > n → index out of bounds

// ⚠ nums.size() - 1 on empty vector wraps to max size_t!
// Always cast: (int)nums.size() - 1