Squared Subsequences - SQRDSUB (Code Chef Easy Question)

Today we will be discussing an easy problem of codechef :-

Here is the link to the Problem

https://www.codechef.com/APRIL20B/problems/SQRDSUB

The logic of the problem is fairly simple.
First , because of constraints we need to solve the problem in atmost O(nlogn) time complexity.

So instead of counting the valid subsequences we count the invalid subsequences and answer as 2^n-invalid .

To be written as a difference of two squares the product should be able to written as (p+q)(p-q);
Hence let the product be a*b .
So a=p+q;
b=p-q;
p=a+b/2;
q=a-b/2;
Hence the product should be able to be expressed as either a product of two odds or a product of two evens , which we check in our function .
As soon as we find a subsequence in which we cant express it as a product of two evens or two odds , we remove it. An odd number can always be written as a difference of two squares.

Here is the C++ code:-
Try to understand it , if you are not able to understand it , then please leave your doubts in the comments.

#include <iostream>
using namespace std;

int main() {
    int t;
    cin>>t;
    while(t--)
    {
        long int n;
        cin>>n;
        long long int arr[n];
        int i=0;
        while(i!=n)
        {
            cin>>arr[i];
            arr[i]=abs(arr[i]);
            i++;
        }
        i=0;
      long long int left=0,right=0,j,k,flag=0;
        long long int ans=n*(n+1)/2;
        i=0;
        while(i!=n)
        {
            left=0;right=0;
            while(arr[i]%4==0 || arr[i]%2!=0)
            {
                i++;
                if(i==n)
                {
                    flag=1;
                    break;
                }
           
            }
            if(flag==1)
            {
                break;
            }
            j=i;
            k=i;
         
            j--;
            left++;
            while(j>-1 && arr[j]%2!=0)
            {
             j--;
             left++;
            }
         
         
         
            i++;
            right++;
            //cout<<"i "<<i;
            while(i<n && arr[i]%2!=0)
            {
                right++;
                i++;
            }
            //cout<<"left "<<left<<" right "<<right;
            ans=ans-(left)*(right);
            //cout<<ans<<" ";
         
        }
        cout<<ans<<endl;
     
    }
// your code goes here
return 0;
}