#include <bits/stdc++.h>
using namespace std;
struct person{
	string name;
	int age;
};
int main() {
	// vector<int> arr={3,2,3,3,2,4};
	// map<int,int> ok;
	// for(int i=0;i<arr.size();i++){
	// 	ok[arr[i]]++;
	// }
	// int maxl,minl,max=0,min=;
	// for(auto it=ok.begin();it!=ok.end();it++){
	// 	cout<<it->first<<"  "<<it->second<<endl;
	// 	if(it->second>max){
	// 		max=it->second;
	// 		maxl=it->first;
	// 	} 
	// 	if(it->second < min){
	// 		min=it->second;
	// 		minl=it->first;
	// 	}
	// }
	// cout<<"maxelement  "<<maxl<<"  freq  "<<max;
	// cout<<"minelement   "<<minl<<"    freq  "<<min;
	
	
	// vector<person> people;
	// people.push_back({"asha",22});
	// people.push_back({"prem",18});
	// people.push_back({"anu",48});
	// for(auto& it:people){
	// 	cout<<(it).name<<endl; //here it is a reference variable
	// }
	
	// map<string,person> ok;
	// ok["asha"]={"asha",22};
	// ok["prem"]={"prem",18};
	// ok["anu"]={"anu",23};
	
	// for(auto& it:ok){
	// 	cout<<it.second.age<<endl;
	// }
	
	// for(auto it=ok.begin();it!=ok.end();it++){
	// 	cout<<it->second.age<<endl;
	// }
	// cout<<ok["asha"].name<<endl;
	
	// --check if there are any two equal numbers in an array at a distance less than or equal to k--
	// brute force o(n2)
	// int arr[]={1,2,1,3,4,2,3,3};
	// int k=2,count=0;
	// for(int i=0;i<7;i++){
	// 	for(int j=i+1;j<=i+k && j<8;j++){
	// 		if(arr[i]==arr[j]){
	// 			count++;
	// 		}
	// 	}
	// }
	// cout<<count;
	
	//hashmap
	// int arr[]={1,2,1,3,4,2,3,3};
	// int k=2,count=0;
	// unordered_map<int,int>ok;
	// for(int i=0;i<8;i++){
	// 	if(ok.find(arr[i])!=ok.end() && i-ok[arr[i]]<=k){
	// 		count++;
	// 	}
	// 	ok[arr[i]]=i;
		
	// }
	// cout<<count<<endl;
	// for(auto it=ok.begin();it!=ok.end();it++){
	// 	cout<<it->first<<"     "<<it->second<<endl;
	// }
	
	
	//count all the i j pairs i<j such that arr[i]+arr[j]==k
	// brute force
	// int arr[]={1,2,1,3,4,2,3,3};
	// int k=3,count=0;
	// for(int i=0;i<8;i++){
	// 	for(int j=i+1;j<8;j++){
	// 		if(arr[i]+arr[j]==k){
	// 			count++;
	// 			cout<<i<<"     "<<j<<endl;
	// 		}
	// 	}
	// }
	// cout<<count<<endl;
	
	//hashmap
	// unordered_map<int,int> ok;
	// int arr[]={1,2,1,3,4,2,3,3};
	// int k=2,count=0;
	// for(int i=0;i<8;i++){
	// 	if(ok.find(k-arr[i])!=ok.end()){
	// 		auto it=ok.find(k-arr[i]);
	// 		count+=it->second;
	// 	}
	// 	ok[arr[i]]++;
	// }
	// cout<<count<<endl;
	
	
	// // count all the i j pairs i<j such that arr[i]-arr[j]==k
	// brute force
	// int arr[]={1,2,1,3,4,2,3,3};
	// int k=1,count=0;
	// for(int i=0;i<8;i++){
	// 	for(int j=i+1;j<8;j++){
	// 		if(arr[i]-arr[j]==k){
	// 			count++;
	// 			cout<<i<<"     "<<j<<endl;
	// 		}
	// 	}
	// }
	// cout<<count<<endl;
	
	
	//hashmap
	// unordered_map<int,int> ok;
	// int arr[]={1,2,1,3,4,2,3,3};
	// int k=1,count=0;
	// for(int i=0;i<8;i++){
	// 	if(ok.find(k+arr[i])!=ok.end()){
	// 		auto it=ok.find(k+arr[i]);
	// 		count+=it->second;
	// 	}
	// 	ok[arr[i]]++;
	// }
	// cout<<count<<endl;
	
	// count all the i j pairs i<j such that abs(arr[i]-arr[j])==k
	// brute force
	// int arr[]={1,2,1,3,4,2,3,3};
	// int k=1,count=0;
	// for(int i=0;i<8;i++){
	// 	for(int j=i+1;j<8;j++){
	// 		if(abs(arr[i]-arr[j])==k){
	// 			count++;
	// 			cout<<i<<"     "<<j<<endl;
	// 		}
	// 	}
	// }
	// cout<<count<<endl;
	
	//hashmap
	// unordered_map<int,int> ok;
	// int arr[]={1,2,1,3,4,2,3,3};
	// int k=1,count=0;
	// for(int i=0;i<8;i++){
	// 	int complement1=arr[i]-k;
	// 	int complement2=k+arr[i];
	// 	if(ok.find(complement1)!=ok.end()){
	// 		count+=ok[complement1];
	// 	}
	// 	if(ok.find(complement2)!=ok.end()){
	// 		count+=ok[complement2];
	// 	}
	// 	ok[arr[i]]++;
		
	// }
	// cout<<count<<endl;

	
	//-------prefix sum--------
	// int arr[]={3,4,1,2,1,4};
	// int l=2 ,r=5;
	// for(int i=1;i<6;i++){
	// 	arr[i]+=arr[i-1];
	// }
	// cout<<arr[r]-arr[l-1];
	
	
	//count the total number of subarrays with sum==k;
	//brute force O(n2)
	// int arr[]={1,0,1,2,0,10,5};
	// int k=4;
	// int count=0;
	// for(int i=0;i<7;i++){
	// 	int sum=arr[i];
	// 	for(int j=i+1;j<7;j++){
	// 		sum+=arr[j];
	// 		if(sum==k){
	// 			count++;
	// 			cout<<i<<"    "<<j<<endl;
				
	// 		}
	// 	}
	// }
	// cout<<count<<endl;
	
	
	//brute force part 2
	// int arr[]={1,0,1,2,0,10,5};
	// int arr1[]={0,0,0,3,0,0,0};
	// int prefix[8]={0}; // prefix sum size will be one more than arr
	// int totalsubarrays=0;
	
	// int k=3;
	// for(int i=1;i<8;i++){
	// 	prefix[i]=prefix[i-1]+arr1[i-1];
	// }
	// int count=0;
	// for(int i=1;i<8;i++){
	// 	for(int j=0;j<=i;j++){
	// 		 if(prefix[i]-k==prefix[j]){
	// 			count++;
	// 			cout<<j<<"    "<<i-1<<endl;
	// 		 }// hume ye to pata hai ki sum ==k to hoga subarray ka
	// 		totalsubarrays++;
	// 	}
	// }
	// cout<<totalsubarrays<<endl;
	// cout<<count<<endl;
	
	
	//hashmap
	// int arr[]={1,0,1,2,0,1,0,5};
	// unordered_map<int,int> ok;
	// ok[0]=1;
	// int sum=0,count=0 ,k=4;
	// for(int i=0;i<8;i++){
	// 	sum+=arr[i];
	// 	if(ok.find(sum-k)!=ok.end()){
	// 		count+=ok[sum-k];
	// 	}
	// 	ok[sum]++;
	// }
	// for(auto it=ok.begin();it!=ok.end();it++){
	// 	cout<<it->first<<"      "<<it->second<<endl;
	// }
	// cout<<count<<endl;
	
	//missing element in an array
	// int arr[]={1};
	// int n=sizeof(arr)/sizeof(arr[0]);
	// unordered_map<int,int> ok;
	// for(int i=0;i<n;i++){
	// 	ok[arr[i]]++;
	// }
	// for(int i=1;i<n+2;i++){
	// 	if(ok.find(i)==ok.end()){
	// 		cout<<i<<endl;
	// 	}
	// }
	
	//find the largest/smallest subarray with sum=k
	
	
	
	
	
	
	
	
	
	
	
	return 0;
}