cout

#include<iostream> using namespace std; const int N = 1e6+10; int n; long long cnt=0…