Given an array of size n, with elements between 1 and n find the maximum number of elements that occur exactly twice in any subarray. Constraints (1 <= n <= 100000)

6
1 3 1 3 2 1
Output: 2 (subarray 1-4, 1-5)

12
5 5 1 3 9 9 9 1 3 5 2 1
Output: 3 (subarray 1-9, 2-10, 2-11)

I have partial points, running O(n^2) solution shown below.

        int ans = 0;
	for(int i = 0; i < n; i++){
		map<int,int> cnt;
		int cans = 0;
		for(int j = i; j < n; j++){
			cnt[arr[j]]++;
			if(cnt[arr[j]] == 2)
				cans++;
			else if(cnt[arr[j]] == 3)
				cans--;
				
			ans = max(ans, cans);
		}
	}
	cout<<ans<<endl;

Any ideas how to solve the problem in O(n log n).