import java.util.Arrays;

/**
 * Created by lidiakulikova on 20/02/2018.
 */
public class Discs {

    public static int solution(int[] A) {
        // 0 <= A.length <= 100,000
        // 0 <= A[i] <= 2147483647
        int [] leftEdge = new int[A.length];
        int [] rightEdge = new int[A.length];

        int maxLength = 100000;
        // maxLength is used to prevent integers > 2147483647
        // and integers < -2147483647
        for (int i = 0; i < A.length; i++) {
            leftEdge[i] = i - A[i];
            rightEdge[i] = i + A[i];
        }
        Arrays.sort(leftEdge);
        Arrays.sort(rightEdge);

        int sum = mergeAndCountOverlaps(leftEdge,rightEdge, maxLength);
        return sum;
    }

    private static int mergeAndCountOverlaps(int[] leftEdge, int[] rightEdge, int maxLength) {
        int leftIndex = 0;
        int rightIndex = 0;
        int sum = 0;
        int total = 0;
        while ((leftIndex < leftEdge.length) || (rightIndex < rightEdge.length)) {
            if ((leftIndex < leftEdge.length) && (rightIndex < rightEdge.length)) {
                boolean compareLeftEdgeandRightEdge;
                if (leftEdge[leftIndex] < -2147483647 + maxLength) {
                    compareLeftEdgeandRightEdge = leftEdge[leftIndex] <= rightEdge[rightIndex];
                } else {
                    compareLeftEdgeandRightEdge = leftEdge[leftIndex] <= rightEdge[rightIndex];
                }
                if (compareLeftEdgeandRightEdge) {
                    // a new left edge
                    sum += total;
                    if (sum > 10000000) {
                        return -1;
                    }
                    total++;
                    leftIndex++;
                } else {
                    // a new right edge
                    total--;
                    rightIndex++;
                }
            } else if (leftIndex < leftEdge.length) {
                // a new left edge
                sum += total;
                if (sum > 10000000) {
                    return -1;
                }
                total++;
                leftIndex++;
            } else if (rightIndex < rightEdge.length) {
                // a new right edge
                total--;
                rightIndex++;
            }
        }
        return sum;
    }


    public static void main (String[] args){
        System.out.println(solution(new int[]{1, 5, 2, 1, 4, 0}));
    }
}