/*
 * Two-pass greedy / 兩趟貪婪：identical algorithm to the C version,
 * but using std::vector for automatic memory management and std::max
 * for clarity. O(n) time, O(n) space.
 */

#include <vector>      // std::vector 動態陣列 / dynamic array
#include <algorithm>   // std::max 取最大值 / max helper

class Solution {
public:
    int candy(std::vector<int>& ratings) {
        int n = static_cast<int>(ratings.size());   // 取大小，轉成 int 避免無號比較 / cast size_t→int
        if (n <= 1) return n;                       // 邊界：0 或 1 個小孩 / edge case

        // vector<int>(n, 1) 建立大小為 n、全部初始化為 1 的向量
        // vector<int>(n, 1) builds a length-n vector with every element = 1 (the floor)
        std::vector<int> left(n, 1);                // 左方向需求 / left-side needs
        std::vector<int> right(n, 1);               // 右方向需求 / right-side needs

        // 第一趟：左到右 / Pass 1: left to right
        for (int i = 1; i < n; ++i) {
            // 評分比左鄰居高 → 糖果至少多 1
            // Higher rating than left neighbor → at least one more candy
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;          // 在前一個基礎 +1 / +1 over previous
            }
            // 否則保持初始的 1 / otherwise keep the initial 1
        }

        // 第二趟：右到左 / Pass 2: right to left
        for (int i = n - 2; i >= 0; --i) {
            // 評分比右鄰居高 → 糖果至少多 1
            // Higher rating than right neighbor → at least one more candy
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;        // 從右側累積 +1 / +1 from the right
            }
        }

        // 把每個位置兩方向的最大值加起來
        // Sum max(left[i], right[i]) over all i
        int total = 0;                              // 總和 / running total
        for (int i = 0; i < n; ++i) {
            total += std::max(left[i], right[i]);   // std::max 取兩者較大者 / pick the larger
        }
        return total;                               // 最少糖果數 / minimum total candies
    }
};