Discover whole variety of positions in all Subarrays such that place and worth are identical

Given an array A[] of dimension N, the duty is to search out the overall variety of positions in all of the subarrays such that the worth and place are the identical.

Examples:

Enter: A[] = {1, 2}
Output: 3

Clarification: Following are the subarrays:

Within the subarray A[1, 1] = [1], elementat place 1 is 1.
Within the subarray A[1, 2] = [1, 2], for each the weather the situation is happy.
Within the subarray A[2, 2] = [2], aspect at place is 2 which is the one aspect.
Therefore the overall positions over all subarrays = 1 + 2 + 0 = 3.

Enter: A[] = {1, 3, 4, 2}
Output: 5

Strategy: The issue may be solved primarily based on the next statement:

Repair some place 1 ≤ i ≤ N and a subarray A[L, R]

Additional, the situation of i being a vaild place is A_i = i − L + 1. Rewriting this situation, we get hold of L = i − A_i + 1, in different phrases, there’s precisely one alternative of L on condition that i is symmetrical.
Nevertheless, we should even have L ≥ 1, so i − A_i + 1 ≥ 1⟺ i ≥ A_i.
The selection of R doesn’t have an effect on i being a symmetrical level, so any R such that R ≥ i works, and there are N − i + 1 of those.

Our closing reply is thus merely the sum of N − i + 1 over all positions 1 ≤ i ≤ N such that A_i ≤ i.

Beneath is the implementation of the above method:

Time Complexity: O(N) 
Auxiliary House: O(1)