โครงสร้างข้อมูล

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += arr[i];
}

for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            std::swap(arr[j], arr[j + 1]);
        }
    }
}

int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

int arr[5] = {10, 20, 30, 40, 50};
cout << arr[0];  // 10
cout << arr[4];  // 50
arr[2] = 100;     // แก้ค่าตำแหน่งที่ 2

#include <vector>

std::vector<int> v;
v.push_back(10);   // [10]
v.push_back(20);   // [10, 20]
v.push_back(30);   // [10, 20, 30]

cout << v.size();      // 3
cout << v[1];          // 20
cout << v.back();      // 30 (ดูตัวสุดท้าย)

v.pop_back();      // ลบตัวสุดท้าย → [10, 20]
v.clear();         // ล้างทั้งหมด → []

// วิธี 1: index
for (size_t i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
}

// วิธี 2: range-based for (C++11)
for (int x : v) {
    cout << x << " ";
}

// วิธี 3: iterator
for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << " ";
}

// Static 2D array
int grid[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

// Dynamic 2D array (vector of vectors)
std::vector<std::vector<int>> mat(
    3, std::vector<int>(4, 0)
);

// การเข้าถึง
mat[1][2] = 99;

// วนลูปผ่านทุกตัว
for (int i = 0; i < (int)mat.size(); i++) {
    for (int j = 0; j < (int)mat[0].size(); j++) {
        cout << mat[i][j] << " ";
    }
    cout << "\n";
}

// C = A × B, ที่ A เป็น m×k, B เป็น k×n, C เป็น m×n
std::vector<std::vector<int>> multiply(
    const std::vector<std::vector<int>>& A,
    const std::vector<std::vector<int>>& B) {
    int m = A.size(), k = A[0].size(), n = B[0].size();
    std::vector<std::vector<int>> C(m, std::vector<int>(n, 0));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            for (int p = 0; p < k; p++)
                C[i][j] += A[i][p] * B[p][j];
    return C;
}

#include <string>

std::string s = "hello";
std::string t = " world";

cout << s.length();          // 5
cout << s[0];                // 'h'
cout << s + t;               // "hello world"
cout << s.substr(1, 3);      // "ell" (เริ่มที่ 1, ยาว 3)

s += "!";                    // "hello!"
s.find("ll");                // 2 (index ที่เริ่ม "ll")
s.find("xyz");               // std::string::npos ถ้าไม่พบ

// เปรียบเทียบ
if (s == "hello!") { /* ... */ }
if (s < "world") { /* ... */ }  // เรียงพจนานุกรม

std::string reverse(std::string s) {
    int n = s.length();
    for (int i = 0; i < n / 2; i++) {
        std::swap(s[i], s[n - 1 - i]);
    }
    return s;
}
// reverse("hello") → "olleh"

std::vector<int> arr = {2, 4, 1, 3, 5};
int n = arr.size();

// prefix[i] = arr[0] + arr[1] + ... + arr[i-1]
std::vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}

// ผลรวมในช่วง [l, r] (inclusive)
auto range_sum = [&](int l, int r) -> long long {
    return prefix[r + 1] - prefix[l];
};

cout << range_sum(1, 3);  // 4 + 1 + 3 = 8

// เพิ่มค่า +5 ในช่วง [2, 4]
int n = 10;
std::vector<int> diff(n + 1, 0);
auto add_range = [&](int l, int r, int x) {
    diff[l] += x;
    diff[r + 1] -= x;
};

add_range(2, 4, 5);
add_range(0, 3, 3);

// สร้าง array จริงจาก difference
std::vector<int> arr(n);
int cur = 0;
for (int i = 0; i < n; i++) {
    cur += diff[i];
    arr[i] = cur;
}

// หาผลรวมสูงสุดของ subarray ที่มีขนาด k พอดี
int max_sum_k(const std::vector<int>& arr, int k) {
    int n = arr.size();
    int cur_sum = 0;
    // ผลรวม k ตัวแรก
    for (int i = 0; i < k; i++) cur_sum += arr[i];
    int max_sum = cur_sum;
    // เลื่อนหน้าต่าง
    for (int i = k; i < n; i++) {
        cur_sum += arr[i] - arr[i - k];
        max_sum = std::max(max_sum, cur_sum);
    }
    return max_sum;
}

// หา substring ที่ยาวที่สุดที่ไม่มีตัวอักษรซ้ำ
int lengthOfLongestSubstring(std::string s) {
    std::vector<int> last_seen(256, -1);
    int left = 0, max_len = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        char c = s[right];
        if (last_seen[c] >= left) {
            left = last_seen[c] + 1;
        }
        last_seen[c] = right;
        max_len = std::max(max_len, right - left + 1);
    }
    return max_len;
}

// หาสองตำแหน่งที่ผลรวม = target ใน array ที่เรียงแล้ว
std::pair<int,int> two_sum_sorted(
    const std::vector<int>& arr, int target) {
    int l = 0, r = arr.size() - 1;
    while (l < r) {
        int sum = arr[l] + arr[r];
        if (sum == target) return {l, r};
        if (sum < target) l++;
        else r--;
    }
    return {-1, -1};  // ไม่พบ
}

// ลบตัวซ้ำใน array ที่เรียงแล้ว ส่งคืนความยาวใหม่
int removeDuplicates(std::vector<int>& nums) {
    if (nums.empty()) return 0;
    int slow = 0;
    for (int fast = 1; fast < (int)nums.size(); fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
    std::vector<std::vector<int>> ans;
    std::sort(nums.begin(), nums.end());
    int n = nums.size();
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;  // ข้ามตัวซ้ำ
        int l = i + 1, r = n - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum == 0) {
                ans.push_back({nums[i], nums[l], nums[r]});
                while (l < r && nums[l] == nums[l+1]) l++;
                while (l < r && nums[r] == nums[r-1]) r--;
                l++; r--;
            } else if (sum < 0) l++;
            else r--;
        }
    }
    return ans;
}

// pi[i] = ความยาวที่ยาวที่สุดของ prefix ของ P ที่เท่ากับ suffix ของ P[0..i]
std::vector<int> build_failure(const std::string& P) {
    int m = P.length();
    std::vector<int> pi(m, 0);
    for (int i = 1; i < m; i++) {
        int j = pi[i - 1];
        while (j > 0 && P[i] != P[j]) j = pi[j - 1];
        if (P[i] == P[j]) j++;
        pi[i] = j;
    }
    return pi;
}

// คืนตำแหน่งเริ่มต้นทั้งหมดที่ P ปรากฏใน T
std::vector<int> kmp_search(
    const std::string& T, const std::string& P) {
    std::vector<int> result;
    if (P.empty()) return result;
    auto pi = build_failure(P);
    int n = T.length(), m = P.length();
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && T[i] != P[j]) j = pi[j - 1];
        if (T[i] == P[j]) j++;
        if (j == m) {
            result.push_back(i - m + 1);
            j = pi[j - 1];
        }
    }
    return result;
}

struct Node {
    int data;
    Node* next;
    Node(int v) : data(v), next(nullptr) {}
};

Node* head = nullptr;
head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
// 10 → 20 → 30 → nullptr

struct DNode {
    int data;
    DNode *prev, *next;
    DNode(int v) : data(v), prev(nullptr), next(nullptr) {}
};

DNode* head = new DNode(10);
DNode* b = new DNode(20);
head->next = b;
b->prev = head;
// head ⇄ b ⇄ nullptr

void delete_node(DNode* node) {
    if (node->prev) node->prev->next = node->next;
    if (node->next) node->next->prev = node->prev;
    delete node;
}
// ใช้เวลา O(1) เพราะเราทราบ prev และ next โดยตรง

#include <list>

std::list<int> lst = {1, 2, 3};
lst.push_back(4);         // {1,2,3,4}
lst.push_front(0);        // {0,1,2,3,4}
lst.pop_back();           // {0,1,2,3}

// แทรกก่อน iterator
auto it = lst.begin();
std::advance(it, 2);
lst.insert(it, 99);       // {0,1,99,2,3}

// ลบที่ iterator
lst.erase(it);            // ลบ "2"

Node* reverse(Node* head) {
    Node *prev = nullptr, *cur = head;
    while (cur) {
        Node* nxt = cur->next;  // เก็บ next ไว้ก่อน
        cur->next = prev;       // สลับทิศ
        prev = cur;
        cur = nxt;
    }
    return prev;  // head ใหม่
}

Node* reverse_recursive(Node* head) {
    if (!head || !head->next) return head;
    Node* new_head = reverse_recursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return new_head;
}

int length(Node* head) {
    int n = 0;
    while (head) {
        n++;
        head = head->next;
    }
    return n;
}

bool hasCycle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

Node* detectCycleStart(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            // เจอจุดเจอกัน ตอนนี้เลื่อน slow กลับ head
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;  // ไม่มี cycle
}

// คืน node ตรงกลาง (ถ้า length คู่ คืนตัวที่สอง)
Node* middleNode(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Node* merge(Node* a, Node* b) {
    Node dummy(0);  // sentinel
    Node* tail = &dummy;
    while (a && b) {
        if (a->data <= b->data) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

Node* sortList(Node* head) {
    if (!head || !head->next) return head;
    // หา mid ด้วย fast-slow
    Node *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    Node* mid = slow->next;
    slow->next = nullptr;  // ตัดครึ่ง
    
    Node* left = sortList(head);
    Node* right = sortList(mid);
    return merge(left, right);
}

struct Node {
    int data;
    Node* next;
    Node(int v) : data(v), next(nullptr) {}
};

Node* make_circular(std::vector<int>& vals) {
    if (vals.empty()) return nullptr;
    Node* head = new Node(vals[0]);
    Node* cur = head;
    for (size_t i = 1; i < vals.size(); i++) {
        cur->next = new Node(vals[i]);
        cur = cur->next;
    }
    cur->next = head;  // ปิดวง
    return head;
}

// Josephus แบบสูตร O(n)
int josephus(int n, int k) {
    int res = 0;  // ฐาน: n=1 ตอบ 0 (index)
    for (int i = 2; i <= n; i++) {
        res = (res + k) % i;
    }
    return res + 1;  // แปลงเป็น 1-indexed
}

#include <stack>

std::stack<int> st;
st.push(10);
st.push(20);
st.push(30);

cout << st.top();    // 30
st.pop();            // ลบ 30
cout << st.top();    // 20
cout << st.size();   // 2
cout << st.empty();  // false (0)

bool isValidParentheses(std::string s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char t = st.top(); st.pop();
            if ((c == ')' && t != '(') ||
                (c == ']' && t != '[') ||
                (c == '}' && t != '{')) return false;
        }
    }
    return st.empty();
}

// คำนวณ postfix เช่น "3 4 + 5 *" = (3+4)*5 = 35
int evalPostfix(std::vector<std::string>& tokens) {
    std::stack<int> st;
    for (auto& t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (t == "+") st.push(a + b);
            else if (t == "-") st.push(a - b);
            else if (t == "*") st.push(a * b);
            else st.push(a / b);
        } else {
            st.push(std::stoi(t));
        }
    }
    return st.top();
}

// สำหรับแต่ละ element หา "element ถัดไปที่ใหญ่กว่า"
// ถ้าไม่มี ให้ใส่ -1
std::vector<int> nextGreater(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> ans(n, -1);
    std::stack<int> st;  // เก็บ index ที่ยังไม่มีคำตอบ
    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[st.top()] < nums[i]) {
            ans[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return ans;
}
// input:  [2, 1, 4, 3, 5]
// output: [4, 4, 5, 5, -1]

int largestRectangleArea(std::vector<int>& heights) {
    heights.push_back(0);  // sentinel ปิดท้าย
    std::stack<int> st;   // index ที่ height เรียง increasing
    int max_area = 0;
    for (int i = 0; i < (int)heights.size(); i++) {
        while (!st.empty() && heights[st.top()] > heights[i]) {
            int h = heights[st.top()]; st.pop();
            int w = st.empty() ? i : i - st.top() - 1;
            max_area = std::max(max_area, h * w);
        }
        st.push(i);
    }
    heights.pop_back();
    return max_area;
}

#include <queue>

std::queue<int> q;
q.push(10);
q.push(20);
q.push(30);

cout << q.front();  // 10
cout << q.back();   // 30
q.pop();            // ลบ 10
cout << q.front();  // 20
cout << q.size();   // 2

#include <deque>

std::deque<int> dq;
dq.push_back(10);    // [10]
dq.push_back(20);    // [10, 20]
dq.push_front(5);    // [5, 10, 20]
dq.push_front(1);    // [1, 5, 10, 20]

cout << dq[2];       // 10 (random access ได้)
cout << dq.front();  // 1
cout << dq.back();   // 20

dq.pop_front();      // ลบ 1 → [5, 10, 20]
dq.pop_back();       // ลบ 20 → [5, 10]

// หาค่ามากสุดในทุก subarray ขนาด k
std::vector<int> maxSlidingWindow(
    std::vector<int>& nums, int k) {
    std::vector<int> ans;
    std::deque<int> dq;  // เก็บ index, ค่าลดลง
    for (int i = 0; i < (int)nums.size(); i++) {
        // ลบ index ที่ออกนอกหน้าต่าง
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        // ลบ index ที่ค่าน้อยกว่า nums[i] (ไม่มีทางเป็น max แล้ว)
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) ans.push_back(nums[dq.front()]);
    }
    return ans;
}

#include <queue>

// Max-heap (default)
std::priority_queue<int> max_pq;
max_pq.push(3);
max_pq.push(1);
max_pq.push(5);
max_pq.push(2);

while (!max_pq.empty()) {
    cout << max_pq.top() << " ";  // 5 3 2 1
    max_pq.pop();
}

// Min-heap
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(3);
min_pq.push(1);
// min_pq.top() == 1

// ใช้กับคู่ (priority, value)
using pii = std::pair<int,int>;  // (distance, node)
std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;
pq.push({10, 1});
pq.push({3, 2});
pq.push({7, 3});
// pop ได้ลำดับ: {3,2}, {7,3}, {10,1}

// แบบง่าย: modulo ด้วยขนาดตาราง
int hash_int(int key, int m) {
    return key % m;  // m ควรเป็นจำนวนเฉพาะ
}

// h(s) = (s[0]*p^(k-1) + s[1]*p^(k-2) + ... + s[k-1]) mod m
long long hash_string(const std::string& s) {
    const long long p = 31;
    const long long m = 1e9 + 9;
    long long h = 0;
    long long p_pow = 1;
    for (char c : s) {
        h = (h + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return h;
}

struct Node {
    int key, value;
    Node* next;
};
Node* table[TABLE_SIZE];

void insert(int key, int value) {
    int idx = hash(key);
    Node* n = new Node{key, value, table[idx]};
    table[idx] = n;
}

// Linear Probing
int find_slot(int key) {
    int i = hash(key);
    while (table[i].occupied && table[i].key != key) {
        i = (i + 1) % TABLE_SIZE;
    }
    return i;
}

#include <unordered_map>

std::unordered_map<std::string, int> mp;
mp["apple"] = 50;
mp["banana"] = 30;
mp.insert({"orange", 40});

// ค้นหา
if (mp.count("apple")) {
    cout << mp["apple"];  // 50
}

// ลูปทุก element (ลำดับไม่ guarantee)
for (auto& [k, v] : mp) {
    cout << k << " = " << v << "\n";
}

// ลบ
mp.erase("banana");

#include <unordered_set>

std::unordered_set<int> s;
s.insert(10);
s.insert(20);
s.insert(10);  // ไม่เพิ่ม (มีอยู่แล้ว)

cout << s.count(10);  // 1
cout << s.size();     // 2
s.erase(10);

// Custom hash สำหรับ int ที่ต้าน collision
struct SafeHash {
    size_t operator()(int x) const {
        // splitmix64
        uint64_t z = (uint64_t)x + 0x9e3779b97f4a7c15ULL;
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
        z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
        return z ^ (z >> 31);
    }
};
std::unordered_map<int, int, SafeHash> safe_map;

// หาสองตัวใน array ที่รวมกันได้ target
std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;  // value → index
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        if (seen.count(need)) {
            return {seen[need], i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

// นับความถี่ของแต่ละ element
std::unordered_map<int, int> freq;
for (int x : arr) {
    freq[x]++;
}
// หา element ที่พบบ่อยที่สุด
int best = -1, best_count = 0;
for (auto& [k, v] : freq) {
    if (v > best_count) {
        best = k;
        best_count = v;
    }
}

// ใช้ hash เก็บผลลัพธ์ที่คำนวณแล้ว
std::unordered_map<long long, long long> memo;
long long fib(long long n) {
    if (n < 2) return n;
    if (memo.count(n)) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

struct Node {
    int key, value;
    Node *prev, *next;
    Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
    int cap;
    Node *head, *tail;  // sentinels
    std::unordered_map<int, Node*> mp;
public:
    LRUCache(int capacity) : cap(capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    
    void remove(Node* n) {
        n->prev->next = n->next;
        n->next->prev = n->prev;
    }
    
    void add_front(Node* n) {
        n->next = head->next;
        n->prev = head;
        head->next->prev = n;
        head->next = n;
    }
    
    int get(int key) {
        if (!mp.count(key)) return -1;
        Node* n = mp[key];
        remove(n);
        add_front(n);
        return n->value;
    }
    
    void put(int key, int value) {
        if (mp.count(key)) {
            Node* n = mp[key];
            n->value = value;
            remove(n);
            add_front(n);
        } else {
            if ((int)mp.size() >= cap) {
                Node* lru = tail->prev;
                mp.erase(lru->key);
                remove(lru);
                delete lru;
            }
            Node* n = new Node(key, value);
            mp[key] = n;
            add_front(n);
        }
    }
};

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

void preorder(TreeNode* root) {
    if (!root) return;
    visit(root);            // root
    preorder(root->left);   // left
    preorder(root->right);  // right
}

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);    // left
    visit(root);            // root
    inorder(root->right);   // right
}

void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);   // left
    postorder(root->right);  // right
    visit(root);             // root
}

#include <queue>
#include <vector>

std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> ans;
    if (!root) return ans;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        std::vector<int> level;
        for (int i = 0; i < sz; i++) {
            TreeNode* n = q.front(); q.pop();
            level.push_back(n->val);
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        ans.push_back(level);
    }
    return ans;
}

void inorder_morris(TreeNode* root) {
    TreeNode* cur = root;
    while (cur) {
        if (!cur->left) {
            visit(cur);
            cur = cur->right;
        } else {
            // หา predecessor ของ cur
            TreeNode* pred = cur->left;
            while (pred->right && pred->right != cur) {
                pred = pred->right;
            }
            if (!pred->right) {
                pred->right = cur;  // สร้าง thread
                cur = cur->left;
            } else {
                pred->right = nullptr;  // ลบ thread
                visit(cur);
                cur = cur->right;
            }
        }
    }
}

TreeNode* search(TreeNode* root, int target) {
    while (root) {
        if (target == root->val) return root;
        root = (target < root->val) ? root->left : root->right;
    }
    return nullptr;  // ไม่พบ
}

TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) root->left = insert(root->left, val);
    else if (val > root->val) root->right = insert(root->right, val);
    // ถ้า val == root->val: ไม่แทรก (no duplicate) หรือจัดการตามปัญหา
    return root;
}

TreeNode* find_min(TreeNode* root) {
    while (root->left) root = root->left;
    return root;
}

TreeNode* remove(TreeNode* root, int val) {
    if (!root) return nullptr;
    if (val < root->val) {
        root->left = remove(root->left, val);
    } else if (val > root->val) {
        root->right = remove(root->right, val);
    } else {
        // พบ node ที่จะลบ
        if (!root->left) {
            TreeNode* r = root->right;
            delete root;
            return r;
        }
        if (!root->right) {
            TreeNode* l = root->left;
            delete root;
            return l;
        }
        // มี 2 child: หา inorder successor
        TreeNode* succ = find_min(root->right);
        root->val = succ->val;
        root->right = remove(root->right, succ->val);
    }
    return root;
}

int height(TreeNode* root) {
    if (!root) return 0;
    return 1 + std::max(height(root->left), height(root->right));
}

// คืน height ถ้า balanced, -1 ถ้าไม่ balanced
int check_balanced(TreeNode* root) {
    if (!root) return 0;
    int lh = check_balanced(root->left);
    if (lh == -1) return -1;
    int rh = check_balanced(root->right);
    if (rh == -1) return -1;
    if (std::abs(lh - rh) > 1) return -1;
    return 1 + std::max(lh, rh);
}
bool isBalanced(TreeNode* root) {
    return check_balanced(root) != -1;
}

int diameter;

int height_for_diameter(TreeNode* root) {
    if (!root) return 0;
    int lh = height_for_diameter(root->left);
    int rh = height_for_diameter(root->right);
    diameter = std::max(diameter, lh + rh);  // path ผ่าน root
    return 1 + std::max(lh, rh);
}

int diameterOfBinaryTree(TreeNode* root) {
    diameter = 0;
    height_for_diameter(root);
    return diameter;
}

bool isValidBST(TreeNode* root, long long lo = LLONG_MIN, long long hi = LLONG_MAX) {
    if (!root) return true;
    if (root->val <= lo || root->val >= hi) return false;
    return isValidBST(root->left, lo, root->val) &&
           isValidBST(root->right, root->val, hi);
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left && right) return root;  // p, q อยู่คนละข้าง
    return left ? left : right;
}

TreeNode* lca_bst(TreeNode* root, TreeNode* p, TreeNode* q) {
    while (root) {
        if (root->val > p->val && root->val > q->val) {
            root = root->left;
        } else if (root->val < p->val && root->val < q->val) {
            root = root->right;
        } else {
            return root;  // p, q อยู่คนละข้าง หรือ root = p หรือ q
        }
    }
    return nullptr;
}

#include <map>

std::map<std::string, int> mp;
mp["apple"] = 50;
mp["banana"] = 30;
mp["cherry"] = 40;

// ค้นหา
auto it = mp.find("apple");
if (it != mp.end()) cout << it->second;  // 50

// ลูปตามลำดับ sorted
for (auto& [k, v] : mp) {
    cout << k << " = " << v << "\n";
}
// apple = 50, banana = 30, cherry = 40 (เรียงตามตัวอักษร)

// หาค่าแรกที่ >= key
auto it2 = mp.lower_bound("banana");
// หาค่าแรกที่ > key
auto it3 = mp.upper_bound("banana");

#include <set>

std::set<int> s = {5, 3, 8, 1, 9};
// ภายในเรียงเป็น {1, 3, 5, 8, 9}

cout << *s.begin();    // 1 (น้อยสุด)
cout << *s.rbegin();   // 9 (มากสุด)

// หา "ค่าถัดไปที่มากกว่า x"
auto it = s.upper_bound(5);
if (it != s.end()) cout << *it;  // 8

std::unordered_map<int, int> in_idx;
int pre_idx;

TreeNode* build(std::vector<int>& pre, int lo, int hi) {
    if (lo > hi) return nullptr;
    int root_val = pre[pre_idx++];
    TreeNode* root = new TreeNode(root_val);
    int mid = in_idx[root_val];
    root->left = build(pre, lo, mid - 1);
    root->right = build(pre, mid + 1, hi);
    return root;
}

TreeNode* buildTree(std::vector<int>& pre, std::vector<int>& ino) {
    int n = ino.size();
    for (int i = 0; i < n; i++) in_idx[ino[i]] = i;
    pre_idx = 0;
    return build(pre, 0, n - 1);
}

// ตัวอย่าง Max-Heap [9, 5, 7, 1, 3, 6]
//
//          9           ← index 0
//        /   \
//       5     7        ← index 1, 2
//      / \   /
//     1   3 6          ← index 3, 4, 5

int parent(int i) { return (i - 1) / 2; }
int left(int i)   { return 2 * i + 1; }
int right(int i)  { return 2 * i + 2; }

class MinHeap {
    std::vector<int> a;
    
    int parent(int i) { return (i - 1) / 2; }
    int left(int i)   { return 2 * i + 1; }
    int right(int i)  { return 2 * i + 2; }
    
    void sift_up(int i) {
        while (i > 0 && a[parent(i)] > a[i]) {
            std::swap(a[parent(i)], a[i]);
            i = parent(i);
        }
    }
    
    void sift_down(int i) {
        int n = a.size();
        while (true) {
            int smallest = i;
            int l = left(i), r = right(i);
            if (l < n && a[l] < a[smallest]) smallest = l;
            if (r < n && a[r] < a[smallest]) smallest = r;
            if (smallest == i) break;
            std::swap(a[i], a[smallest]);
            i = smallest;
        }
    }
public:
    void push(int x) {
        a.push_back(x);
        sift_up(a.size() - 1);
    }
    
    int top() { return a[0]; }
    
    void pop() {
        a[0] = a.back();
        a.pop_back();
        if (!a.empty()) sift_down(0);
    }
    
    bool empty() { return a.empty(); }
    int size() { return a.size(); }
    
    void build(std::vector<int>& v) {
        a = v;
        for (int i = (int)a.size() / 2 - 1; i >= 0; i--) {
            sift_down(i);
        }
    }
};

void heap_sort(std::vector<int>& a) {
    int n = a.size();
    
    // Build max-heap (in-place)
    auto sift_down = [&](int i, int heap_size) {
        while (true) {
            int l = 2*i+1, r = 2*i+2, largest = i;
            if (l < heap_size && a[l] > a[largest]) largest = l;
            if (r < heap_size && a[r] > a[largest]) largest = r;
            if (largest == i) break;
            std::swap(a[i], a[largest]);
            i = largest;
        }
    };
    
    for (int i = n/2 - 1; i >= 0; i--) sift_down(i, n);
    
    // Extract ทีละตัว
    for (int i = n - 1; i > 0; i--) {
        std::swap(a[0], a[i]);  // ส่ง max ไปท้าย
        sift_down(0, i);
    }
}

// หา k element ที่มากสุดใน array
std::vector<int> topK(std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    // min-heap ขนาด k
    for (int x : nums) {
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();  // เอาตัวน้อยสุดออก
    }
    std::vector<int> ans;
    while (!pq.empty()) { ans.push_back(pq.top()); pq.pop(); }
    return ans;
}

struct ListNode {
    int val;
    ListNode *next;
};

struct Cmp {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;  // min-heap
    }
};

ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    std::priority_queue<ListNode*, std::vector<ListNode*>, Cmp> pq;
    for (auto* h : lists) if (h) pq.push(h);
    
    ListNode dummy(0), *tail = &dummy;
    while (!pq.empty()) {
        ListNode* n = pq.top(); pq.pop();
        tail->next = n;
        tail = n;
        if (n->next) pq.push(n->next);
    }
    return dummy.next;
}

std::vector<long long> dijkstra(
    int src, int n,
    std::vector<std::vector<std::pair<int,int>>>& adj) {
    
    std::vector<long long> dist(n, LLONG_MAX);
    std::priority_queue<std::pair<long long,int>,
                       std::vector<std::pair<long long,int>>,
                       std::greater<>> pq;
    dist[src] = 0;
    pq.push({0, src});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;  // เป็น entry เก่า
        for (auto& [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

class MedianFinder {
    std::priority_queue<int> max_heap;  // ครึ่งซ้าย (≤ median)
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
public:
    void addNum(int num) {
        if (max_heap.empty() || num <= max_heap.top()) {
            max_heap.push(num);
        } else {
            min_heap.push(num);
        }
        // balance
        if (max_heap.size() > min_heap.size() + 1) {
            min_heap.push(max_heap.top());
            max_heap.pop();
        } else if (min_heap.size() > max_heap.size()) {
            max_heap.push(min_heap.top());
            min_heap.pop();
        }
    }
    
    double findMedian() {
        if (max_heap.size() > min_heap.size()) return max_heap.top();
        return (max_heap.top() + min_heap.top()) / 2.0;
    }
};

// graph ที่มี V vertices (เก็บ weight, 0 = ไม่มี edge)
int V;
int adj[1000][1000];  // หรือ vector<vector<int>>

void add_edge(int u, int v, int w) {
    adj[u][v] = w;
    // adj[v][u] = w;  // ถ้า undirected
}

bool has_edge(int u, int v) {
    return adj[u][v] != 0;
}

// weighted graph
int V;
std::vector<std::vector<std::pair<int,int>>> adj;
// adj[u] = list ของ (v, weight)

void init(int n) {
    V = n;
    adj.assign(n, {});
}

void add_edge(int u, int v, int w) {
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});  // ถ้า undirected
}

// ไล่ neighbors ของ u
for (auto& [v, w] : adj[u]) {
    // ...
}

struct Edge {
    int u, v, w;
};

std::vector<Edge> edges;
edges.push_back({0, 1, 5});
edges.push_back({1, 2, 3});

// ใช้ใน Kruskal: sort by weight
std::sort(edges.begin(), edges.end(),
          [](const Edge& a, const Edge& b) { return a.w < b.w; });

std::vector<int> bfs(int src, const std::vector<std::vector<int>>& adj) {
    int n = adj.size();
    std::vector<int> dist(n, -1);
    std::vector<int> parent(n, -1);
    std::queue<int> q;
    
    dist[src] = 0;
    q.push(src);
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {  // ยังไม่เคยเยี่ยม
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }
    return dist;  // dist[v] = ระยะสั้นสุดจาก src → v
}

std::vector<int> reconstruct(int src, int target,
                              const std::vector<int>& parent) {
    std::vector<int> path;
    for (int cur = target; cur != -1; cur = parent[cur]) {
        path.push_back(cur);
        if (cur == src) break;
    }
    std::reverse(path.begin(), path.end());
    return path;
}

std::vector<bool> visited;

void dfs(int u, const std::vector<std::vector<int>>& adj) {
    visited[u] = true;
    // visit(u) — ประมวลผล u
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, adj);
        }
    }
}

void traverse(int n, const std::vector<std::vector<int>>& adj) {
    visited.assign(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfs(i, adj);
    }
}

void dfs_iter(int src, const std::vector<std::vector<int>>& adj) {
    std::vector<bool> visited(adj.size(), false);
    std::stack<int> st;
    st.push(src);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        // visit(u)
        for (int v : adj[u]) {
            if (!visited[v]) st.push(v);
        }
    }
}

enum State { WHITE, GRAY, BLACK };  // ยังไม่เยี่ยม / กำลัง / เสร็จ

bool dfs_cycle(int u, const std::vector<std::vector<int>>& adj,
               std::vector<State>& state) {
    state[u] = GRAY;
    for (int v : adj[u]) {
        if (state[v] == GRAY) return true;  // back edge → cycle
        if (state[v] == WHITE && dfs_cycle(v, adj, state)) {
            return true;
        }
    }
    state[u] = BLACK;
    return false;
}

bool has_cycle(int n, const std::vector<std::vector<int>>& adj) {
    std::vector<State> state(n, WHITE);
    for (int i = 0; i < n; i++) {
        if (state[i] == WHITE && dfs_cycle(i, adj, state)) {
            return true;
        }
    }
    return false;
}

void dfs_topo(int u, const std::vector<std::vector<int>>& adj,
              std::vector<bool>& visited, std::vector<int>& order) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs_topo(v, adj, visited, order);
    }
    order.push_back(u);  // เพิ่มหลัง dfs ลูกเสร็จ
}

std::vector<int> topological_sort(int n,
                                  const std::vector<std::vector<int>>& adj) {
    std::vector<bool> visited(n, false);
    std::vector<int> order;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfs_topo(i, adj, visited, order);
    }
    std::reverse(order.begin(), order.end());
    return order;
}

std::vector<int> kahn(int n, std::vector<std::vector<int>>& adj) {
    std::vector<int> in_degree(n, 0);
    for (int u = 0; u < n; u++) {
        for (int v : adj[u]) in_degree[v]++;
    }
    
    std::queue<int> q;
    for (int i = 0; i < n; i++) {
        if (in_degree[i] == 0) q.push(i);
    }
    
    std::vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (--in_degree[v] == 0) q.push(v);
        }
    }
    
    if ((int)order.size() != n) {
        // มี cycle — topological sort ไม่ได้
        return {};
    }
    return order;
}

std::vector<long long> bellman_ford(
    int src, int n, const std::vector<std::tuple<int,int,int>>& edges) {
    // edges = list of (u, v, w)
    std::vector<long long> dist(n, LLONG_MAX);
    dist[src] = 0;
    
    // relax ทุก edge V-1 ครั้ง
    for (int i = 0; i < n - 1; i++) {
        for (auto& [u, v, w] : edges) {
            if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    
    // ตรวจ negative cycle
    for (auto& [u, v, w] : edges) {
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
            // มี negative cycle!
            return {};
        }
    }
    return dist;
}

// dist[i][j] = shortest path จาก i → j
void floyd_warshall(std::vector<std::vector<long long>>& dist) {
    int n = dist.size();
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != LLONG_MAX && dist[k][j] != LLONG_MAX) {
                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

// การใช้งาน: เริ่มต้น dist[i][i] = 0, dist[i][j] = weight, dist[i][j] = INF ถ้าไม่มี edge

#include <algorithm>
// สมมติมี DSU จากบทที่ 10

long long kruskal(int n, std::vector<std::tuple<int,int,int>>& edges) {
    // edges = list of (w, u, v) — sort ด้วย w
    std::sort(edges.begin(), edges.end());
    
    DSU dsu(n);
    long long total = 0;
    int edges_used = 0;
    
    for (auto& [w, u, v] : edges) {
        if (dsu.find(u) != dsu.find(v)) {
            dsu.unite(u, v);
            total += w;
            edges_used++;
            if (edges_used == n - 1) break;  // MST สมบูรณ์
        }
    }
    
    if (edges_used != n - 1) return -1;  // graph ไม่ connected
    return total;
}

long long prim(int n, std::vector<std::vector<std::pair<int,int>>>& adj) {
    std::vector<long long> min_w(n, LLONG_MAX);
    std::vector<bool> in_mst(n, false);
    min_w[0] = 0;
    
    std::priority_queue<std::pair<long long,int>,
                       std::vector<std::pair<long long,int>>,
                       std::greater<>> pq;
    pq.push({0, 0});
    
    long long total = 0;
    while (!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        if (in_mst[u]) continue;
        in_mst[u] = true;
        total += w;
        for (auto& [v, weight] : adj[u]) {
            if (!in_mst[v] && weight < min_w[v]) {
                min_w[v] = weight;
                pq.push({weight, v});
            }
        }
    }
    return total;
}

int timer = 0;
std::vector<int> disc, low, on_stack;
std::stack<int> st;
std::vector<std::vector<int>> sccs;

void tarjan(int u, const std::vector<std::vector<int>>& adj) {
    disc[u] = low[u] = timer++;
    st.push(u);
    on_stack[u] = true;
    
    for (int v : adj[u]) {
        if (disc[v] == -1) {
            tarjan(v, adj);
            low[u] = std::min(low[u], low[v]);
        } else if (on_stack[v]) {
            low[u] = std::min(low[u], disc[v]);
        }
    }
    
    if (low[u] == disc[u]) {
        std::vector<int> scc;
        while (true) {
            int v = st.top(); st.pop();
            on_stack[v] = false;
            scc.push_back(v);
            if (v == u) break;
        }
        sccs.push_back(scc);
    }
}

std::vector<std::vector<int>> find_sccs(int n,
        const std::vector<std::vector<int>>& adj) {
    disc.assign(n, -1);
    low.assign(n, -1);
    on_stack.assign(n, false);
    sccs.clear();
    timer = 0;
    for (int i = 0; i < n; i++) {
        if (disc[i] == -1) tarjan(i, adj);
    }
    return sccs;
}

class DSU {
    std::vector<int> parent;
public:
    DSU(int n) : parent(n) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int x) {
        while (parent[x] != x) x = parent[x];
        return x;
    }
    
    void unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra != rb) parent[ra] = rb;
    }
};

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

class DSU {
    std::vector<int> parent, sz;
public:
    DSU(int n) : parent(n), sz(n, 1) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;  // อยู่ set เดียวกัน
        if (sz[ra] < sz[rb]) std::swap(ra, rb);
        parent[rb] = ra;
        sz[ra] += sz[rb];
        return true;
    }
    
    bool connected(int a, int b) {
        return find(a) == find(b);
    }
    
    int size(int x) {
        return sz[find(x)];
    }
};

bool has_cycle(int n, std::vector<std::pair<int,int>>& edges) {
    DSU dsu(n);
    for (auto& [u, v] : edges) {
        if (dsu.connected(u, v)) return true;  // มี cycle
        dsu.unite(u, v);
    }
    return false;
}

std::vector<int> components(int n, std::vector<std::pair<int,int>>& edges) {
    DSU dsu(n);
    for (auto& [u, v] : edges) dsu.unite(u, v);
    
    std::vector<int> comp_id(n);
    for (int i = 0; i < n; i++) comp_id[i] = dsu.find(i);
    return comp_id;
}

class DSU_Rollback {
    std::vector<int> parent, rank_;
    std::stack<std::tuple<int,int,int,int>> history;  // (a, pa, b, pb)
public:
    DSU_Rollback(int n) : parent(n), rank_(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int x) {
        while (parent[x] != x) x = parent[x];
        return x;  // ไม่ compress path
    }
    
    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) {
            history.push({-1, -1, -1, -1});  // mark no-op
            return false;
        }
        if (rank_[ra] < rank_[rb]) std::swap(ra, rb);
        history.push({ra, parent[ra], rb, parent[rb]});
        parent[rb] = ra;
        if (rank_[ra] == rank_[rb]) rank_[ra]++;
        return true;
    }
    
    void rollback() {
        auto [a, pa, b, pb] = history.top();
        history.pop();
        if (a == -1) return;  // no-op
        parent[b] = pb;
        parent[a] = pa;
        if (rank_[a] > 0 && parent[a] == a) rank_[a]--;
    }
};

struct AVLNode {
    int val, height;
    AVLNode *left, *right;
    AVLNode(int v) : val(v), height(1), left(nullptr), right(nullptr) {}
};

int height(AVLNode* n) { return n ? n->height : 0; }
int bf(AVLNode* n) { return n ? height(n->left) - height(n->right) : 0; }
void update(AVLNode* n) {
    n->height = 1 + std::max(height(n->left), height(n->right));
}

AVLNode* rotate_right(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* t2 = x->right;
    x->right = y;
    y->left = t2;
    update(y); update(x);
    return x;  // root ใหม่
}

AVLNode* rotate_left(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* t2 = y->left;
    y->left = x;
    x->right = t2;
    update(x); update(y);
    return y;
}

AVLNode* insert(AVLNode* root, int val) {
    if (!root) return new AVLNode(val);
    if (val < root->val) root->left = insert(root->left, val);
    else if (val > root->val) root->right = insert(root->right, val);
    else return root;
    
    update(root);
    int balance = bf(root);
    
    // Left-Left
    if (balance > 1 && val < root->left->val)
        return rotate_right(root);
    // Right-Right
    if (balance < -1 && val > root->right->val)
        return rotate_left(root);
    // Left-Right
    if (balance > 1 && val > root->left->val) {
        root->left = rotate_left(root->left);
        return rotate_right(root);
    }
    // Right-Left
    if (balance < -1 && val < root->right->val) {
        root->right = rotate_right(root->right);
        return rotate_left(root);
    }
    return root;
}

struct TrieNode {
    TrieNode* children[26];
    bool is_end;
    TrieNode() : is_end(false) {
        for (int i = 0; i < 26; i++) children[i] = nullptr;
    }
};

class Trie {
    TrieNode* root;
public:
    Trie() : root(new TrieNode()) {}
    
    void insert(const std::string& word) {
        TrieNode* cur = root;
        for (char c : word) {
            int i = c - 'a';
            if (!cur->children[i]) cur->children[i] = new TrieNode();
            cur = cur->children[i];
        }
        cur->is_end = true;
    }
    
    bool search(const std::string& word) {
        TrieNode* cur = root;
        for (char c : word) {
            int i = c - 'a';
            if (!cur->children[i]) return false;
            cur = cur->children[i];
        }
        return cur->is_end;
    }
    
    bool startsWith(const std::string& prefix) {
        TrieNode* cur = root;
        for (char c : prefix) {
            int i = c - 'a';
            if (!cur->children[i]) return false;
            cur = cur->children[i];
        }
        return true;
    }
};

int n;
std::vector<long long> tree;  // size 4n

void build(const std::vector<int>& arr, int node, int lo, int hi) {
    if (lo == hi) { tree[node] = arr[lo]; return; }
    int mid = (lo + hi) / 2;
    build(arr, 2*node, lo, mid);
    build(arr, 2*node+1, mid+1, hi);
    tree[node] = tree[2*node] + tree[2*node+1];
}

void update(int node, int lo, int hi, int idx, int val) {
    if (lo == hi) { tree[node] = val; return; }
    int mid = (lo + hi) / 2;
    if (idx <= mid) update(2*node, lo, mid, idx, val);
    else update(2*node+1, mid+1, hi, idx, val);
    tree[node] = tree[2*node] + tree[2*node+1];
}

long long query(int node, int lo, int hi, int l, int r) {
    if (r < lo || hi < l) return 0;  // outside
    if (l <= lo && hi <= r) return tree[node];  // fully inside
    int mid = (lo + hi) / 2;
    return query(2*node, lo, mid, l, r) +
           query(2*node+1, mid+1, hi, l, r);
}

// Wrapper
void init(const std::vector<int>& arr) {
    n = arr.size();
    tree.assign(4 * n, 0);
    build(arr, 1, 0, n - 1);
}
void update(int idx, int val) { update(1, 0, n - 1, idx, val); }
long long query(int l, int r) { return query(1, 0, n - 1, l, r); }

class Fenwick {
    std::vector<long long> bit;
    int n;
public:
    Fenwick(int n) : n(n), bit(n + 1, 0) {}
    
    // เพิ่ม delta ที่ตำแหน่ง idx (1-indexed)
    void update(int idx, long long delta) {
        for (; idx <= n; idx += idx & -idx) {
            bit[idx] += delta;
        }
    }
    
    // ผลรวมตั้งแต่ 1 ถึง idx (prefix sum)
    long long query(int idx) {
        long long sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += bit[idx];
        }
        return sum;
    }
    
    // ผลรวมในช่วง [l, r] (1-indexed)
    long long range_query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

// นับ inversion: คู่ (i,j) ที่ i < j และ arr[i] > arr[j]
long long count_inversions(std::vector<int> arr) {
    int n = arr.size();
    
    // compress ค่าให้อยู่ใน [1, n]
    std::vector<int> sorted = arr;
    std::sort(sorted.begin(), sorted.end());
    sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
    for (int& x : arr) {
        x = std::lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;
    }
    
    Fenwick fw(n);
    long long inv = 0;
    for (int i = n - 1; i >= 0; i--) {
        // นับจำนวนตัวที่น้อยกว่า arr[i] ที่เห็นแล้ว (อยู่ขวา)
        inv += fw.query(arr[i] - 1);
        fw.update(arr[i], 1);
    }
    return inv;
}

class SparseTable {
    std::vector<std::vector<int>> table;
    std::vector<int> log2;
public:
    void build(const std::vector<int>& arr) {
        int n = arr.size();
        log2.assign(n + 1, 0);
        for (int i = 2; i <= n; i++) log2[i] = log2[i / 2] + 1;
        
        int K = log2[n] + 1;
        table.assign(K, std::vector<int>(n));
        for (int i = 0; i < n; i++) table[0][i] = arr[i];
        
        for (int k = 1; k < K; k++) {
            for (int i = 0; i + (1 << k) <= n; i++) {
                table[k][i] = std::min(
                    table[k-1][i],
                    table[k-1][i + (1 << (k-1))]
                );
            }
        }
    }
    
    int query(int l, int r) {  // [l, r] inclusive
        int k = log2[r - l + 1];
        return std::min(table[k][l], table[k][r - (1 << k) + 1]);
    }
};

std::vector<int> build_suffix_array(const std::string& s) {
    int n = s.size();
    std::vector<int> sa(n), rank(n), tmp(n);
    
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s[i];
    }
    
    for (int k = 1; k < n; k *= 2) {
        auto cmp = [&](int a, int b) {
            if (rank[a] != rank[b]) return rank[a] < rank[b];
            int ra = (a + k < n) ? rank[a + k] : -1;
            int rb = (b + k < n) ? rank[b + k] : -1;
            return ra < rb;
        };
        std::sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
        }
        rank = tmp;
    }
    return sa;
}

// lcp[i] = longest common prefix ของ sa[i] และ sa[i-1]
std::vector<int> build_lcp(const std::string& s, const std::vector<int>& sa) {
    int n = s.size();
    std::vector<int> rank(n), lcp(n, 0);
    for (int i = 0; i < n; i++) rank[sa[i]] = i;
    
    int h = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] > 0) {
            int j = sa[rank[i] - 1];
            while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
            lcp[rank[i]] = h;
            if (h > 0) h--;
        }
    }
    return lcp;
}

int LOG;
std::vector<std::vector<int>> up;  // up[u][k] = 2^k ancestor ของ u
std::vector<int> depth;

void preprocess(int n, const std::vector<std::vector<int>>& children) {
    LOG = std::__lg(n) + 1;
    up.assign(n, std::vector<int>(LOG, -1));
    depth.assign(n, 0);
    
    // BFS หา depth และ up[u][0] = parent[u]
    std::queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : children[u]) {
            depth[v] = depth[u] + 1;
            up[v][0] = u;
            q.push(v);
        }
    }
    
    // สร้าง table
    for (int k = 1; k < LOG; k++) {
        for (int u = 0; u < n; u++) {
            if (up[u][k-1] != -1) {
                up[u][k] = up[up[u][k-1]][k-1];
            }
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) std::swap(u, v);
    int diff = depth[u] - depth[v];
    
    // เลื่อน u ขึ้นจนเท่า v
    for (int k = 0; k < LOG; k++) {
        if ((diff >> k) & 1) u = up[u][k];
    }
    
    if (u == v) return u;
    
    // เลื่อนทั้งคู่ขึ้นพร้อมกัน
    for (int k = LOG - 1; k >= 0; k--) {
        if (up[u][k] != up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }
    }
    return up[u][0];
}

int n;
std::vector<std::vector<int>> adj;
std::vector<int> parent, depth, heavy, head, pos, sz;
int cur_pos;

int dfs(int u) {
    sz[u] = 1;
    int max_sz = 0;
    heavy[u] = -1;
    for (int v : adj[u]) {
        if (v == parent[u]) continue;
        parent[v] = u;
        depth[v] = depth[u] + 1;
        int v_sz = dfs(v);
        sz[u] += v_sz;
        if (v_sz > max_sz) {
            max_sz = v_sz;
            heavy[u] = v;
        }
    }
    return sz[u];
}

void decompose(int u, int h) {
    head[u] = h;
    pos[u] = cur_pos++;
    if (heavy[u] != -1) decompose(heavy[u], h);  // ต่อ chain
    for (int v : adj[u]) {
        if (v != parent[u] && v != heavy[u]) {
            decompose(v, v);  // เริ่ม chain ใหม่
        }
    }
}

// Path query จาก a ไป b (สมมติใช้ segment tree)
int query_path(int a, int b) {
    int res = 0;  // identity
    while (head[a] != head[b]) {
        if (depth[head[a]] < depth[head[b]]) std::swap(a, b);
        // query chain [pos[head[a]], pos[a]]
        res = combine(res, seg_query(pos[head[a]], pos[a]));
        a = parent[head[a]];
    }
    if (depth[a] > depth[b]) std::swap(a, b);
    // query ส่วนสุดท้าย [pos[a], pos[b]]
    res = combine(res, seg_query(pos[a], pos[b]));
    return res;
}

struct Query {
    int l, r, idx;
};

std::vector<int> mo_algorithm(std::vector<int>& arr,
                              std::vector<Query>& queries) {
    int n = arr.size();
    int block = std::max(1, (int)std::sqrt(n));
    
    // sort queries
    std::sort(queries.begin(), queries.end(),
        [block](const Query& a, const Query& b) {
            int ba = a.l / block, bb = b.l / block;
            if (ba != bb) return ba < bb;
            // parity optimization: even block sort r asc, odd desc
            return (ba & 1) ? a.r > b.r : a.r < b.r;
        });
    
    std::vector<int> freq(*std::max_element(arr.begin(), arr.end()) + 1, 0);
    std::vector<int> ans(queries.size());
    int cur_l = 0, cur_r = -1, cur_distinct = 0;
    
    auto add = [&](int x) {
        if (freq[x] == 0) cur_distinct++;
        freq[x]++;
    };
    auto remove = [&](int x) {
        freq[x]--;
        if (freq[x] == 0) cur_distinct--;
    };
    
    for (auto& q : queries) {
        while (cur_l > q.l) add(arr[--cur_l]);
        while (cur_r < q.r) add(arr[++cur_r]);
        while (cur_l < q.l) remove(arr[cur_l++]);
        while (cur_r > q.r) remove(arr[cur_r--]);
        ans[q.idx] = cur_distinct;
    }
    return ans;
}

struct Node {
    int val;
    Node *left, *right;
    Node(int v = 0) : val(v), left(nullptr), right(nullptr) {}
};

Node* build(const std::vector<int>& arr, int lo, int hi) {
    Node* n = new Node;
    if (lo == hi) { n->val = arr[lo]; return n; }
    int mid = (lo + hi) / 2;
    n->left = build(arr, lo, mid);
    n->right = build(arr, mid + 1, hi);
    n->val = n->left->val + n->right->val;
    return n;
}

// Update: สร้าง path ใหม่เฉพาะส่วนที่เปลี่ยน
Node* update(Node* prev, int lo, int hi, int idx, int val) {
    Node* n = new Node(*prev);  // copy
    if (lo == hi) { n->val = val; return n; }
    int mid = (lo + hi) / 2;
    if (idx <= mid) {
        n->left = update(prev->left, lo, mid, idx, val);
    } else {
        n->right = update(prev->right, mid + 1, hi, idx, val);
    }
    n->val = n->left->val + n->right->val;
    return n;
}

int query(Node* n, int lo, int hi, int l, int r) {
    if (!n || r < lo || hi < l) return 0;
    if (l <= lo && hi <= r) return n->val;
    int mid = (lo + hi) / 2;
    return query(n->left, lo, mid, l, r) +
           query(n->right, mid + 1, hi, l, r);
}

// ตัวอย่างการใช้งาน
std::vector<Node*> versions;
versions.push_back(build(arr, 0, n - 1));
versions.push_back(update(versions[0], 0, n - 1, 3, 99));
// query version 0: ผลรวมใน [l, r]
query(versions[0], 0, n - 1, l, r);
// query version 1 หลัง update
query(versions[1], 0, n - 1, l, r);

std::vector<std::vector<int>> adj;
std::vector<bool> removed;
std::vector<int> sz;

int dfs_size(int u, int p) {
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v != p && !removed[v]) {
            sz[u] += dfs_size(v, u);
        }
    }
    return sz[u];
}

int find_centroid(int u, int p, int tree_size) {
    for (int v : adj[u]) {
        if (v != p && !removed[v] && sz[v] > tree_size / 2) {
            return find_centroid(v, u, tree_size);
        }
    }
    return u;
}

void decompose(int u) {
    int tree_size = dfs_size(u, -1);
    int c = find_centroid(u, -1, tree_size);
    removed[c] = true;
    
    // ประมวลผลที่ centroid c
    // (เช่น นับ path ที่ผ่าน c)
    
    // recurse บนแต่ละ component
    for (int v : adj[c]) {
        if (!removed[v]) decompose(v);
    }
}