Oracle OA-5 2023

Problem Description

In an organization, there are n servers, each with a capacity of capacity[i]. A contiguous subsegment [l, r] of servers is said to be stable if capacity[l] = capacity[r] = sum[l+1, r-1]. In other words, the capacity of the servers at the endpoints of the segment should be equal to the sum of the capacities of all the interior servers.

Find the number of stable sub-segments of length 3 or more.

Constraints

1 <= n <= 3*10^5
1 <= capacity[i] ≤ 10^9

Example

Input: n = 7, capacity = [9, 3, 1, 2, 3, 9, 10]
Output: 2
Explanation: The stable segments are: [9, 3, 1, 2, 3, 9] and [3, 1, 2, 3]

• [9, 3, 1, 2, 3, 9]:
  Here, the first and last elements are both 9, and the sum of the interior elements (3 + 1 + 2 + 3) equals 9, making this a stable subsegment.
• [3, 1, 2, 3]:
  The first and last elements are both 3, and the sum of the interior elements (1 + 2) equals 3, making this another stable subsegment.

Thus, there are 2 stable sub-segments of length 3 or more.