Given an array arr of n integers, find the number of its subarrays such that removing the subarray creates a non-empty array that is sorted in increasing order. Note: A subarray is defined as any contiguous segment of the array.

Constraints

• 1 ≤ n ≤ 2×10⁵
• 1 ≤ arr[i] ≤ 10⁹

Example 1

Input:

arr = [1, 2, 1, 2]

Output:

7

Explanation: There are 7 subarrays that on removal produce a non-empty sorted array. Hence, the answer is 7. The subarrays [3], [3, 1] and [1, 2] give a non-empty sorted array on removal.

Example 2

Input:

arr = [3, 1, 2]

Output:

3

Explanation: The subarrays [3], [3, 1] and [1, 2] give a non-empty sorted array on removal.

Example 3

Input:

arr = [1, 2, 2, 6, 1, 3]

Output:

10

Explanation: The subarrays [1, 2, 2, 6], [1, 2, 2, 6, 1], [2, 2, 6], [2, 2, 6, 1], [2, 6], [2, 6, 1], [6], [6, 1], [1, 3] and [1] give a non-empty sorted array on removal.

解法

先求最长严格递增的前缀长度 L(arr[0..L-1])，后缀长度 R(arr[n-R..n-1])。枚举保留的左前缀长度 i(从 0 到 L)，用双指针在右后缀里找最小 j 使 arr[n-1-j] > arr[i-1](i=0 时无下界)。答案 = Σ (R - j + 1)，需去掉空子数组并保证移除非空。O(n)。

from typing import List

def countRemovableSubarrays(arr: List[int]) -> int:
    n = len(arr)
    # 找最长严格递增前缀长度 L
    L = 1
    while L < n and arr[L] > arr[L - 1]:
        L += 1
    if L == n:
        # 整体已严格递增，任意非空子数组都满足
        return n * (n + 1) // 2
    # 找最长严格递增后缀长度 R
    R = 1
    while R < n and arr[n - R - 1] < arr[n - R]:
        R += 1
    # 双指针：保留左 i 个 + 保留右 j 个，要求 arr[i-1] < arr[n-j]
    ans = 0
    j = R
    for i in range(L + 1):
        while j > 0 and (i > 0 and arr[n - j] <= arr[i - 1]):
            j -= 1
        # 移除子数组 = arr[i..n-j-1]，长度 = n - j - i，必须非空 → j + i < n
        if i + j < n:
            ans += 1  # 这个唯一切分对应 1 个子数组
        else:
            # 切分使得"移除"是空，跳过
            pass
    # 上面的方法只数了 (i, j) 对应的 (start=i, end=n-j-1) 子数组数；但题目允许扩张
    # 实际：对每个左保留长度 i，合法的 j 范围 [j_min(i), R]，每个 j 对应一个子数组
    # 重新写：
    ans = 0
    j_ptr = R
    for i in range(L + 1):
        # 找最大的 j 使 arr[n-j] > arr[i-1] (i==0 时任何 j 都行)
        while j_ptr > 0 and i > 0 and arr[n - j_ptr] <= arr[i - 1]:
            j_ptr -= 1
        max_j = j_ptr
        # j 可以从 0 到 max_j；要求移除非空：i + j < n
        upper = min(max_j, n - i - 1)
        if upper >= 0:
            ans += upper + 1
    return ans

class Solution {
    long countRemovableSubarrays(int[] arr) {
        int n = arr.length;
        int L = 1;
        while (L < n && arr[L] > arr[L - 1]) L++;
        if (L == n) return (long) n * (n + 1) / 2;
        int R = 1;
        while (R < n && arr[n - R - 1] < arr[n - R]) R++;
        long ans = 0;
        int jPtr = R;
        for (int i = 0; i <= L; i++) {
            while (jPtr > 0 && i > 0 && arr[n - jPtr] <= arr[i - 1]) jPtr--;
            int maxJ = jPtr;
            int upper = Math.min(maxJ, n - i - 1);
            if (upper >= 0) ans += upper + 1;
        }
        return ans;
    }
}

class Solution {
public:
    long long countRemovableSubarrays(vector<int>& arr) {
        int n = arr.size();
        int L = 1;
        while (L < n && arr[L] > arr[L - 1]) L++;
        if (L == n) return (long long) n * (n + 1) / 2;
        int R = 1;
        while (R < n && arr[n - R - 1] < arr[n - R]) R++;
        long long ans = 0;
        int jPtr = R;
        for (int i = 0; i <= L; i++) {
            while (jPtr > 0 && i > 0 && arr[n - jPtr] <= arr[i - 1]) jPtr--;
            int maxJ = jPtr;
            int upper = min(maxJ, n - i - 1);
            if (upper >= 0) ans += upper + 1;
        }
        return ans;
    }
};

There is a straight line of students of various heights. The students' heights are given in the form of an array, in the order they are standing in the line. Consider the region of a student as the length of the largest subarray that includes that student's position, and in which that student's height is equal to maximum height among all students present in that subarray. Return the sum of the region of all students. Function Description Complete the function calculateTotalRegion in the editor. calculateTotalRegion has the following parameter(s):

• heights: an array of the heights of students standing in the line Returns long integer: the desired sum of all regions

Constraints

• 1 ≤ length of heights ≤ 10⁵
• 1 ≤ heights[i] ≤ 10⁹

Example 1

Input:

heights = [3, 5, 6]

Output:

6

Explanation: The longest subarray in which the first student's height is equal to the maximum height among all other students is [3]; thus, the length of the region of the first student is 1. The longest subarray in which the second student's height is equal to maximum height among all other students is [3, 5]; thus, the length of the region of the second student is 2. The longest subarray in which the third student's height is equal to the maximum height among all other students is [3, 5, 6]; thus, the length of the region of the third student is 3. Thus, the sum of the lengths of all regions of all students is 1 + 2 + 3 = 6.

Example 2

Input:

heights = [1, 2, 1]

Output:

5

Explanation: Subarrays for values 1, 2, and 1 are [1], [1, 2], and [1]. The sum of their lengths is 1 + 3 + 1 = 5.

解法

单调栈：对每个 i 求其作为最大值时左右能延伸到的最远边界 left[i], right[i]，region 长度 = right[i] - left[i] + 1。累加。O(n)。

from typing import List

def calculateTotalRegion(heights: List[int]) -> int:
    n = len(heights)
    left = [0] * n   # 最远左下标 (>= 0)
    right = [n - 1] * n
    stack = []
    for i in range(n):
        # 严格大才弹出，相等的也归入同一组（避免重复，使用 ≥ / >）
        while stack and heights[stack[-1]] < heights[i]:
            stack.pop()
        left[i] = stack[-1] + 1 if stack else 0
        stack.append(i)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] <= heights[i]:
            stack.pop()
        right[i] = stack[-1] - 1 if stack else n - 1
        stack.append(i)
    return sum(right[i] - left[i] + 1 for i in range(n))

import java.util.*;

class Solution {
    long calculateTotalRegion(int[] heights) {
        int n = heights.length;
        int[] left = new int[n], right = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && heights[st.peek()] < heights[i]) st.pop();
            left[i] = st.isEmpty() ? 0 : st.peek() + 1;
            st.push(i);
        }
        st.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && heights[st.peek()] <= heights[i]) st.pop();
            right[i] = st.isEmpty() ? n - 1 : st.peek() - 1;
            st.push(i);
        }
        long ans = 0;
        for (int i = 0; i < n; i++) ans += right[i] - left[i] + 1;
        return ans;
    }
}

class Solution {
public:
    long long calculateTotalRegion(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n);
        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && heights[st.top()] < heights[i]) st.pop();
            left[i] = st.empty() ? 0 : st.top() + 1;
            st.push(i);
        }
        while (!st.empty()) st.pop();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && heights[st.top()] <= heights[i]) st.pop();
            right[i] = st.empty() ? n - 1 : st.top() - 1;
            st.push(i);
        }
        long long ans = 0;
        for (int i = 0; i < n; i++) ans += right[i] - left[i] + 1;
        return ans;
    }
};

You are given a 0-indexed array of positive integers nums. A subarray of nums is called incremovable if nums becomes strictly increasing on removing the subarray. For example, the subarray [3, 4] is an incremovable subarray of [5, 3, 4, 6, 7] because removing this subarray changes the array [5, 3, 4, 6, 7] to [5, 6, 7], which is strictly increasing. Return the total number of incremovable subarrays of nums. Note that an empty array is considered strictly increasing. A subarray is a contiguous non-empty sequence of elements within an array.

Constraints

• `1

Example 1

Input:

nums = [1,2,3,4]

Output:

10

Explanation: The 10 incremovable subarrays are: [1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], and [1,2,3,4], because on removing any one of these subarrays nums becomes strictly increasing. Note that you cannot select an empty subarray.

Example 2

Input:

nums = [6,5,7,8]

Output:

7

Explanation: The 7 incremovable subarrays are: [5], [6], [5,7], [6,5], [5,7,8], [6,5,7], and [6,5,7,8]. It can be shown that there are only 7 incremovable subarrays in nums.

Example 3

Input:

nums = [8,7,6,6]

Output:

3

Explanation: The 3 incremovable subarrays are: [8,7,6], [7,6,6], and [8,7,6,6]. Note that [8,7] is not an incremovable subarray because after removing [8,7] nums becomes [6,6], which is sorted in ascending order but not strictly increasing.

解法

同 LC 2972：先求最长严格递增前缀 L 与后缀 R。若整体已严格递增，答案 n*(n+1)/2。否则枚举保留的左长度 i(0..L)，双指针找最大 j 使 nums[n-j] > nums[i-1]，累加 j + 1(去除前缀+后缀的所有"中间删除"方案)。O(n)。

from typing import List

def incremovableSubarrayCount(nums: List[int]) -> int:
    n = len(nums)
    L = 1
    while L < n and nums[L] > nums[L - 1]:
        L += 1
    if L == n:
        return n * (n + 1) // 2
    # 最长严格递增后缀
    R = 1
    while R < n and nums[n - R - 1] < nums[n - R]:
        R += 1
    ans = R + 1  # i = 0 时，j ∈ [0..R]
    # 双指针
    j_ptr = R
    for i in range(1, L + 1):
        while j_ptr > 0 and nums[n - j_ptr] <= nums[i - 1]:
            j_ptr -= 1
        max_j = j_ptr
        upper = min(max_j, n - i - 1)  # 移除非空
        if upper >= 0:
            ans += upper + 1
    return ans

class Solution {
    long incremovableSubarrayCount(int[] nums) {
        int n = nums.length;
        int L = 1;
        while (L < n && nums[L] > nums[L - 1]) L++;
        if (L == n) return (long) n * (n + 1) / 2;
        int R = 1;
        while (R < n && nums[n - R - 1] < nums[n - R]) R++;
        long ans = R + 1;
        int jPtr = R;
        for (int i = 1; i <= L; i++) {
            while (jPtr > 0 && nums[n - jPtr] <= nums[i - 1]) jPtr--;
            int maxJ = jPtr;
            int upper = Math.min(maxJ, n - i - 1);
            if (upper >= 0) ans += upper + 1;
        }
        return ans;
    }
}

class Solution {
public:
    long long incremovableSubarrayCount(vector<int>& nums) {
        int n = nums.size();
        int L = 1;
        while (L < n && nums[L] > nums[L - 1]) L++;
        if (L == n) return (long long) n * (n + 1) / 2;
        int R = 1;
        while (R < n && nums[n - R - 1] < nums[n - R]) R++;
        long long ans = R + 1;
        int jPtr = R;
        for (int i = 1; i <= L; i++) {
            while (jPtr > 0 && nums[n - jPtr] <= nums[i - 1]) jPtr--;
            int maxJ = jPtr;
            int upper = min(maxJ, n - i - 1);
            if (upper >= 0) ans += upper + 1;
        }
        return ans;
    }
};

Given an array arr, you can perform the following operation:

• Remove an element from any position in the array. The order of other elements should be maintained after removing the element. You're allowed to perform this operation until the arr size becomes 1. Now the beauty of an array is equal to the number of elements where a[i] = i (the array is 1 indexed). Given an array, find the maximum beauty after performing the above operation. Function Description Complete the function findMaximumBeauty in the editor. findMaximumBeauty has the following parameter:
• int[] arr: an array of integers Returns int: the maximum beauty of the array

Constraints

unknown for now

Example 1

Input:

arr = [1, 3, 2, 5, 4, 5, 3]

Output:

4

Explanation: Following the operations described in the problem statement:

• Remove the first 3, then arr becomes [1, 2, 5, 4, 5, 3].
• Remove 3, then arr becomes [1, 2, 5, 4, 5]. The beauty of the final array is 4. (where a[i] = i).

A mathematics professor in a Senior Secondary High School decided to evaluate students for the Teachers Assessment based on their problem-solving skills. Given an array of integers arr, and an integer, sumVal, the task is to pair the elements in arr into interesting pairs. Find the number of interesting pairs in the array. An unordered pair (i, j) is defined to be interesting if |arr[i] - arr[j]| + |arr[i] + arr[j]|, the sum of absolute difference and absolute sum at the values in respective indices, is equal to sumVal. The goal is to find the number of interesting pairs in the array.

Example 1

Input:

arr = [1, 4, -1, 2]
sumVal = 4

Output:

2

Explanation: There are two interesting pairs, (1, 4) and (3, 4) because: |arr[1] - arr[4]| + |arr[1] + arr[4]| = |1 - 2| + |1 + 2| = 1 + 3 = 4. |arr[3] - arr[4]| + |arr[3] + arr[4]| = |-1 - 2| + |-1 + 2| = 3 + 1 = 4.

Given an array arr of n integers, choose any two of the first three elements of the array and remove them. The cost of such an operation is the maximum of the two elements removed. For example, in the array [1, 2, 3, 4, 5], (1, 3) can be removed at a cost of 3, (1, 2) can be removed at a cost of 2 but (2, 4) cannot be removed as 4 is not amongst the first three elements of the array. If there are less than three elements left in the array, remove all of them at a cost of the maximum of the remaining values. Find the minimum cost to remove all the elements from the array. Function Description Complete the function getMinCost in the editor. getMinCost has the following parameter:

• int arr[n]: an array of integers Returns int: the minimum cost to remove all the elements from the array

Constraints

• 1 ≤ n ≤ 10³
• 1 ≤ arr[i] ≤ 10⁶

The data analysts of Hackerland want to schedule some long running tasks on remote servers optimally to minimize the cost of running them locally. The analysts have two servers, a paid one and a free one. The free server can be used only if the paid server is occupied. The task is expected to take time units of time to complete and the cost of processing the task on the paid server is cost. The task can be run on the free server only if some task is already running on the paid server. The cost of the free server is 0 and it can process any task in 1 unit of time. Find the minimum cost to complete all the tasks if tasks are scheduled optimally. Function Description Complete the function getMinimumCost in the editor. getMinimumCost has the following parameters:

• 1. int[] time: an array of integers representing the time units required for each task
• 2. int[] cost: an array of integers representing the cost of processing each task on the paid server Returns int: the minimum cost to complete all tasks

Given an array a, create another array b where b[i] is the size of the maximum subarray which includes a[i] and a[i] is the maximum element in that subarray. Return the sum of all elements of array b. Function Description Complete the function maximumSizeSubarraySum in the editor. maximumSizeSubarraySum has the following parameter:

• int a[]: an array of integers Returns int: the sum of all elements of array b

Constraints

a.length ≤ 10⁵

Example 1

Input:

a = {10, 20, 10, 9, 12, 14}

Output:

17

Explanation: The sum of all elements of array b is 1 + 6 + 2 + 1 + 3 + 4 = 17.

Considering a lane to be one-dimensional, you are provided with an array police_station consisting of n distinct integers representing the coordinates of police stations. You, as a prosperous individual, aspire to acquire exactly capacity distinct properties across the entirety of this one-dimensional lane (which may be located anywhere on the number line), with the condition that they do not coincide with the coordinates of any police station and neither any older property acquired. The cost associated with purchasing a property is determined by its minimum distance from any police station. The total cost incurred will be the sum of costs associated with purchasing each property. Here distance between x1 and x2 means the absolute difference of x1 and x2 (i.e. |x1-x2|) Given police_station an array containing the coordinates of the police stations, and capacity indicates the total number of distinct properties you can acquire. Your task is to calculate the total minimum cost to acquire exactly the capacity number of properties. Function Description Complete the function minAcquireCost in the editor. minAcquireCost takes the following arguments:

• int police_station[n]: the input array police station containing the coordinates of all the police stations.
• int capacity: the total number of distinct properties you can acquire Returns int: the total minimum cost to acquire exactly the capacity number of properties

Constraints

An unknown urban legend for now

Example 1

Input:

police_station = [7, 8]
capacity = 4

Output:

6

Explanation: Suppose n=2, police_station = [7, 8], and capacity = 4. The coordinates of your property will be [5, 6, 9, 10] for minimum cost. So, the answer is sum of |7 - 5| + |7 - 6| + |8 - 9| + |8 - 10| = 6.

From an array source of n integers, in a single operation, choose any even-length subarray. Alternately add and subtract 1 from each element of the subarray from left to right. For example, for source = [1, 2, 3, 4, 5, 6] the subarray [3, 4, 5, 6] can be chosen and made [3+1, 4-1, 5+1, 6-1]=[4, 3, 6, 5]. Then source = [1, 2, 4, 3, 6, 5]. Given two arrays source and target of n integers, find the minimum number of operations that must be performed on the array source to make it equal to the array target. Report -1 if it is not possible to make the two arrays equal. Function Description Complete the function minOperations in the editor. minOperations has the following parameters:

• 1. int[] source: an array of integers
• 2. int[] target: an array of integers Returns int: the minimum number of operations, or -1 if it's not possible

Constraints

• `1

There is an integer array arr of length n. Two arrays b and c are called a perfect break of arr if: The lengths of arrays b and c are n. Elements in array b are in non-decreasing order. Elements in array c are in non-increasing order. They satisfy b[i] ≥ 0, c[i] ≥ 0, and b[i] + c[i] = arr[i], for each i where 0 ≤ i Function Description Complete the function perfectBreakin the editor.perfectBreakhas the following parameter:int arr[n]`: the num of possible perfect breaks modulo (10⁹ + 7).

Constraints

• 1 ≤ n ≤ 3000
• 1 ≤ arr[i] ≤ 3000

Example 1

Input:

arr = [2, 3, 2]

Output:

4

Explanation: There are 4 possible perfect breaks of array arr:

• b = [0, 1, 1], c = [2, 2, 1] is a perfect break because it
• b and c have 3 elements
• b is non-decreasing order
• c is in non-increasing order
• elements of b and c are 0 or more than the sums of a[i] + b[i] = [2, 3, 2], which matches arr.
• b = [0, 1, 2], c = [2, 2, 0] is a perfect break.
• b = [0, 2, 2], c = [2, 1, 0] is a perfect break.
• b = [1, 2, 2], c = [1, 1, 0] is a perfect break.
• b = [1, 3, 2], c = [1, 0, 0] is not a perfect break because b is not non-decreasing.
• b = [1, 2, 2], c = [2, 1, 0] is not a perfect break because b[0] + c[0] ≠ arr[0].

Example 2

Input:

arr = [3, 2]

Output:

6

Explanation: The perfect breaks are: b = [0, 0], c = [3, 2] b = [0, 1], c = [3, 1] b = [0, 2], c = [3, 0] b = [1, 1], c = [2, 1] b = [1, 2], c = [2, 0] b = [2, 2], c = [1, 0]

Given a tree of g_nodes nodes rooted at 0, each node has a value given in array A. There is also a parameter, K. An unweighted undirected tree is represented with g_nodes nodes numbered from 0 to g_nodes - 1 and g_edges = g_nodes - 1 edges where the ith edge connects the nodes numbered g_from[i] to g_to[i]. Each node numbered u is associated with a value represented by A[u]. Collect all of the values at the nodes using one of two methods: Collect A[j] - K points. Collect floor(A[j]/2) points. If this method is chosen, all values of node j in this node's subtree are changed to the floor(A[j]/2) as well. You can only collect the value at a node if its parent's value has been collected before (except the root). You have to maximize the total points collected. Note: It is possible that the accumulated value may be negative at some point. Function Description Complete the function treePoints in the editor. treePoints has the following parameters:

• int g_nodes: the number of nodes in the graph
• int g_from[g_nodes - 1]: one end of each edge
• int g_to[g_nodes - 1]: the other end each edge
• int A[g_nodes]: the values at the nodes
• int K: the cost to collect a full value Returns long: the maximum sum of values that can be collected

Constraints

• 1 ≤ g_nodes ≤ 10⁵
• g_edges = g_nodes - 1
• 0 ≤ g_from[i], g_to[i] < g_nodes
• g_from[i] ≠ g_to[i]
• 1 ≤ A[i] ≤ 10⁹
• 1 ≤ K ≤ 10⁹

Example 1

Input:

g_nodes = 4
g_from = [0, 1, 2]
g_to = [1, 2, 3]
A = [10, 10, 3, 3]
K = 5

Output:

11

Explanation: The first line shows the initial tree. Nodes are labeled as <node number>:<node value>. Darker nodes are ones that change in an operation. For the first two values, reduce them by K = 5 and collect them. When the value at node 2 is collected as floor(3/2), the value at nodes j below it are changed using the same method, floor(A[j]/2). Hence, the value at node 3 is changed to 1. The value at node 3 is then collected using the second method as floor(1/2). The total collected is 5 + 5 + 1 + 0 = 11.