There is a small, one-way bridge that can carry a maximum weight of U units at a time. A line of N cars is waiting with weights weight[0..N-1] (entering in that order).

At most two cars can be on the bridge at once. To begin, the first two cars enter. After that, car k enters as soon as car k - 2 leaves (i.e., the bridge always holds two consecutive cars from the kept sequence). Cars leave in entry order.

If at any moment the total weight on the bridge would exceed U, some drivers have to turn back. A driver who turns back is removed from the line and never tries again. Return the minimum number of drivers that must turn back so the bridge is never overloaded.

Constraints

1 ≤ N ≤ 100000, 1 ≤ weight[i] ≤ 10⁹, 1 ≤ U ≤ 10⁹.

Examples:

• U = 9, weight = [5, 3, 8, 1, 8, 7, 7, 6] → 4. Remaining [5, 3, 1, 6] crosses safely.
• U = 7, weight = [7, 6, 5, 2, 7, 4, 5, 4] → 5. Remaining [5, 2, 4].
• U = 7, weight = [3, 4, 3, 1] → 0.
• U = 2, weight = [3, 7, 5, 5, 6, 3, 9, 10, 8, 4] → 10 (every weight > U).

解法

保留一个保持原顺序的子序列，要求：(1) 每个保留的重量 ≤ U；(2) 任意相邻两个保留之和 ≤ U。求最少去除数。贪心从左到右扫描，维护 prev = 上一辆保留车的重量；prev + w > U 时退掉更重的那辆，让保留邻居尽量轻。单车 w > U 一定退。复杂度 O(N)。

def min_turn_back(U, weight):
    turnbacks = 0
    prev = None
    for w in weight:
        if w > U:
            turnbacks += 1
            continue
        if prev is None:
            prev = w
        elif prev + w <= U:
            prev = w
        else:
            turnbacks += 1
            if w < prev:
                prev = w
    return turnbacks

class Solution {
    public int solution(int U, int[] weight) {
        int turnbacks = 0;
        long prev = -1;
        for (int w : weight) {
            if (w > U) { turnbacks++; continue; }
            if (prev < 0) { prev = w; }
            else if (prev + w <= U) { prev = w; }
            else {
                turnbacks++;
                if (w < prev) prev = w;
            }
        }
        return turnbacks;
    }
}

int solution(int U, vector<int>& weight) {
 int turnbacks = 0;
 long long prev = -1;
 for (int w : weight) {
 if (w > U) { turnbacks++; continue; }
 if (prev < 0) prev = w;
 else if (prev + w <= U) prev = w;
 else {
 turnbacks++;
 if (w < prev) prev = w;
 }
 }
 return turnbacks;
}

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem. Implement an LRU (Least Recently Used) cache that supports: LRUCache(capacity): initialize the cache with the given positive capacity. get(key): return the value if the key exists and mark it as most recently used; otherwise return -1. put(key, value): insert or update the key with the value and mark it as most recently used; if the cache exceeds capacity, evict the least recently used entry. Requirements: Target time complexity: O(1) per get/put. Constraints Number of operations: 1 ≤ N ≤ 2 * 10⁵ key, value are 32-bit integers Input: capacity=2 put(1,1) put(2,2) get(1) put(3,3) get(2) put(4,4) get(1) get(3) get(4) Output: 1 -1 3 4 Input: capacity=1 put(1,1) put(2,2) get(1) get(2) Output: -1 2 Input: capacity=2 put(1,1) put(1,10) get(1) Output: 10 Input: capacity=3 get(42) Output: -1 Input: capacity=2 put(1,1) put(2,2) put(3,3) get(1) get(2) get(3) Output: -1 2 3 Example Input capacity=2 put(1,1) put(2,2) get(1) put(3,3) get(2) put(4,4) get(1) get(3) get(4) Output 1 -1 3 4 Function Description Complete solveLRUCacheOperations. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.

Constraints

Use the limits and requirements stated in the prompt.

Example 1

Input:

input = "capacity=2\nput(1,1)\nput(2,2)\nget(1)\nput(3,3)\nget(2)\nput(4,4)\nget(1)\nget(3)\nget(4)"

Output:

["1", "-1", "-1", "3", "4"]

Explanation: The returned string array must match the expected standard output lines for the sample input.