Sonic has an array of length N. He wants to count the number of subarrays where the number of primes is equal to the number of non-primes. As the number of such subarrays can be large, help him calculate the value.
Note :
Subarray : Contains all elements between indices i and j (inclusive) such that, 1 <= i <= j <= N.
Input Format :
The first line contains N denoting the size of the array.
N integers follow in the next line denoting the array elements.
Output Format :
Print the answer to the required problem.
Note :
C and C++ users use long long int data type to print the answer.
Java users use long data type to print the answer.
Constraints:
1 <= N <= 105
1 <= array elements <= 105
Possible subarrays are:
{1, 1, 2, 2}
{1, 2}
{2, 2, 5, 8, 8, 8}
{2, 5, 8, 8}
{5, 8}
{1, 1, 2, 2, 5, 8}
{1, 2, 2, 5, 8, 8}
