I am solving https://codeforces.com/contest/1556/problem/C. I got an idea to use Stacks and Prefix Sums to find the answer, However, it is failing on test case 13.

My Approach: 1. Iterate from left to right and calculate prefix sum of length upto index i.

1. Iterate from left to right and insert extra open brackets in stack with it's location i.

2. When we get extra closing, pop the stack and match closing with opening.

3. In every iteration insert matching subarray in a list, because we can use this to calculate number of ways to group matching subarrays.