Berland starts to seize the initiative on the war with Flatland. To drive the enemy from…
- User
Berland starts to seize the initiative on the war with Flatland. To drive the enemy from their native land, the berlanders need to know exactly how many more flatland soldiers are left in the enemy's reserve. Fortunately, the scouts captured an enemy in the morning, who had a secret encrypted message with the information the berlanders needed so much.
The captured enemy had an array of positive integers. Berland intelligence have long been aware of the flatland code: to convey the message, which contained a number m, the enemies use an array of integers a. The number of its subarrays, in which there are at least k equal numbers, equals m. The number k has long been known in the Berland army so General Touristov has once again asked Corporal Vasya to perform a simple task: to decipher the flatlanders' message.
Help Vasya, given an array of integers a and number k, find the number of subarrays of the array of numbers a, which has at least k equal numbers.
Subarray a[i... j] (1 ≤ i ≤ j ≤ n) of array a = (a1, a2, ..., an) is an array, made from its consecutive elements, starting from the i-th one and ending with the j-th one: a[i... j] = (ai, ai + 1, ..., aj). Input
The first line contains two space-separated integers n, k (1 ≤ k ≤ n ≤ 4·105), showing how many numbers an array has and how many equal numbers the subarrays are required to have, correspondingly.
The second line contains n space-separated integers ai (1 ≤ ai ≤ 109) — elements of the array.
Output
Print the single number — the number of such subarrays of array a, that they have at least k equal integers.
Please do not use the %lld specifier to read or write 64-bit integers in С++. In is preferred to use the cin, cout streams or the %I64d specifier.
Examples
Input
4 2 1 2 1 2
Output
3
Input
5 3 1 2 1 1 3
Output
2
Input
3 1 1 1 1
Output
6
Note
In the first sample are three subarrays, containing at least two equal numbers: (1,2,1), (2,1,2) and (1,2,1,2).
In the second sample are two subarrays, containing three equal numbers: (1,2,1,1,3) and (1,2,1,1).
In the third sample any subarray contains at least one 1 number. Overall they are 6: (1), (1), (1), (1,1), (1,1) and (1,1,1).
Assistant
We need count number of subarrays of array a (size n) that have at least k equal numbers (i.e., there exists some value that appears at least k times in the subarray). Equivalent to: count number of pairs (l, r) with 1 ≤ l ≤ r ≤ n such that the subarray a[l..r] contains some value with frequency ≥ k.
Constraints: n up to 4e5, k up to n. Need O(n log n) or O(n) solution.
This is a classic problem: number of subarrays with at least k equal elements. Usually solved by two pointers: for each left index l, find minimal r such that subarray a[l..r] has some value appearing at least k times. Then any r' >= r also satisfies condition, so contribute (n - r + 1). Sum over l.
But careful: The condition is existence of some value with frequency >= k, not necessarily a specific value. So we can maintain frequencies for current window [l, r], and check if any frequency >= k. However maintaining max frequency efficiently is tricky; we can use two pointers with a counter of "satisfied" values? The condition is at least one value reaching k. As we expand r, we increment frequency of a[r]. When any frequency reaches k, we know window satisfies. Then for a given l, we want the smallest r such that condition holds. Then we can increment l, decrement frequency of a[l], and maybe condition becomes false again, so we need to expand r again.
But note: when we have a window [l, r] that satisfies condition, moving l forward may cause the condition to stop being satisfied if the value that reached k loses one occurrence and its count becomes k-1, and no other value has count >= k. In that case we need to move r forward until condition re-satisfies (or until end). This is a typical two-pointer O(n) if we can update the condition efficiently. However we need to know if there exists any value with frequency >= k after each decrement. That could be done by maintaining a count of values that have frequency >= k. Let cnt[x] be frequency in current window. Let good = number of distinct values with cnt[x] >= k. Then condition is good > 0. When we increment a[r], we update cnt and if cnt becomes exactly k then good++. When we decrement a[l], if cnt becomes k-1 then good--. That's O(1) per step. Since we only move l and r from 1 to n, total O(n). This works because frequencies are updated per step.
Thus algorithm:
Initialize l = 1, r = 0, cnt map (use unordered_map because a_i up to 1e9, but n 4e5, so map okay), good = 0. ans = 0 (long long). For l from 1 to n: while r < n and good == 0: r++ cnt[a[r]]++ if cnt[a[r]] == k: good++ if good > 0: ans += n - r + 1 // because any r' >= r works // Now move l forward: // remove a[l] from window: if cnt[a[l]] == k: good-- // because after decrement it will be k-1? Actually we decrement after checking; we need to adjust good before we decrement? Let's think: we have current window [l, r]. We'll remove a[l] and then l becomes l+1. So before removal, we check condition for current l. Then we need to update counts for next iteration. So after counting ans, we do: cnt[a[l]]-- if cnt[a[l]] == k-1: good-- // But careful: when cnt is exactly k before decrement, after decrement it becomes k-1. So if cnt[a[l]] == k before decrement, good--. Alternatively, we can check if cnt[a[l]] == k before decrement, then good-- after decrement? Actually we can decrement then check if new count is k-1? But if cnt[a[l]] was k, after decrement becomes k-1, so we should decrement good. So: if cnt[a[l]] == k: good--; // before decrement? Actually before decrement, cnt[a[l]] is the frequency in window. If it's exactly k, then after removal it will become k-1, meaning it no longer meets condition. So good--. So we do: if cnt[a[l]] == k: good--; cnt[a[l]]--; // after check. // However we also need to handle the case when cnt[a[l]] > k? If cnt > k before decrement, after decrement it may still be >= k, so good unchanged. So we check if cnt[a[l]] == k. // But careful: if cnt[a[l]] was k+? Actually if it was >k, after decrement it still >=k, so good unchanged. So condition is if cnt[a[l]] == k before decrement, then removal makes it k-1, so good--. // Also, note that if cnt[a[l]] < k, removal has no effect on good. // So after decrement, we move l.
But we must ensure that when we increment r we check good. When we increment, we increase cnt[a[r]]. If it becomes k, then good++.
Potential pitfall: Good is number of distinct values with count >= k. But if a value appears many times and we increment from k-1 to k, good++. If we increment from k to k+1, good unchanged. So all fine.
Edge Cases: If k = 1, then any non-empty subarray qualifies because it contains at least 1 element, and that element's count is at least 1, so >=1. So answer is n*(n+1)/2. That matches example: n=3 => 6. Our two-pointer would also work: Initially good=0. For l=1, we will expand r until good>0. As we add first element, cnt becomes 1, which is ==k? For k=1, yes, good++. So r=1, good>0, ans+= n - r + 1 = 3. Then remove a[1]: cnt[a[1]]==k (1) => good--, cnt--. Now good=0. Then l=2, r currently =1 (since we haven't moved r). While good==0 and r<n, r++ to 2, cnt becomes 1 => good++ => good>0, ans+= n - 2 + 1 = 2 => total 5? Actually we need to get 6. Let's simulate:
n=3, k=1, a: [1,1,1] Initialize l=1, r=0, good=0, ans=0. l=1: while r<3 and good==0: r=1, cnt[1]=1, if cnt==1 => good=1 ans+= n - r + 1 = 3 -1 +1=3 => ans=3 Then removal: before decrement cnt[1]=1 == k? yes => good-- => good=0; cnt[1]-- => cnt[1]=0. l=2: while r<3 and good==0: r=2, cnt[1]=1, if cnt==1 => good=1 ans+= n - r + 1 = 3-2+1=2 => ans=5 removal: before decrement cnt[1]=1 == k? yes => good-- => good=0; cnt[1]-- => cnt[1]=0. l=3: while r<3 and good==0? r currently 2, r<3 true, good==0 true: r=3, cnt[1]=1 => good=1 ans+= n - r + 1 = 3-3+1=1 => ans=6 removal: before decrement cnt[1]=1 => good-- =>0; cnt[1]-- =>0. l=4 (loop ends) So ans=6. Works.
Now, check example1: n=4, k=2, a=[1,2,1,2] Initialize l=1, r=0, good=0, ans=0. l=1: while r<4 and good==0: r=1: cnt1=1, not k => good=0 r=2: cnt2=1? Actually a[2]=2, cnt2=1, still no k. good=0 r=3: a[3]=1, cnt1 becomes 2, which is k => good=1 Stop since good>0. ans+= n - r +1 = 4-3+1=2 => ans=2? Wait expected answer is 3. Let's compute manually: subarrays with at least 2 equal numbers: (1,2,1) (2,1,2) (1,2,1,2). That's 3. Our ans for l=1 gave 2 (r=3 gives subarrays (1,2,1) and (1,2,1,2)? Actually for l=1, minimal r is 3, then all r>=3 (i.e., r=3 and r=4) give valid subarrays: [1..3] and [1..4] => 2 subarrays. That's correct contributions from l=1. l=2: before moving, we need to remove a[1] from window. Current window: [1,3] with cnt: 1->2, 2->1. good=1 because 1 appears 2. Removal: cnt[1] was 2 == k? yes => good-- => good=0. cnt[1]-- => becomes 1. Now window effectively [2,3] (since l=2, r=3) but we haven't yet moved r; but we just removed element. Now l=2 (starting loop). good==0. While r<4 and good==0: r=4: cnt[2]++ (a[4]=2). cnt[2] becomes 2, which is k => good=1. Now r=4. ans+= n - r + 1 = 4-4+1=1 => ans=3. Then removal for l=2: cnt[2] before decrement? In window [2,4] cnt: 1:1, 2:2. good=1 because 2 appears twice. Remove a[2]=2: cnt[2]==k? yes, good-- => good=0, cnt[2]-- => becomes1. l=3: now window [3,4] with cnt: 1:1, 2:1, good=0. While r<4 and good==0: r is already 4, so loop not entered. So good==0, no ans addition. Then removal: cnt[1] before decrement? cnt[1]=1 <k so good unchanged; cnt[1]-- => 0. l=4: window [4,4] cnt: 2:1, good=0, r=4, while condition false, ans+=0. Removal: etc. Total ans=3. Works.
Example2: n=5, k=3, a=[1,2,1,1,3] Expect 2. Simulate: Initialize l=1, r=0, good=0. l=1: while good==0 and r<5: r=1: cnt1=1 r=2: cnt2=1 r=3: cnt1=2 r=4: cnt1=3 -> good=1 (since cnt1 reaches 3) r=4, ans+=5-4+1=2 (subarrays: [1..4] and [1..5]) => ans=2? But answer is 2. That's it? But there might be also l=2? Let's continue to see if there are more contributions. Remove a[1]: cnt1 before decrement is 3 == k => good-- =>0; cnt1-- =>2. Window now [2,4] with cnt1=2, cnt2=1, good=0. l=2: while good==0 and r<5: r=5: cnt3=1? a[5]=3, cnt3=1. Still no freq>=3. good=0. r=5 reached, but good still 0. So no ans addition for l=2. So ans stays 2. But expected answer is 2. So matches.
So algorithm yields correct results.
But careful: The while loop condition is r < n and good == 0. That ensures we keep expanding until condition satisfied or we hit end. But when we hit end without satisfying condition, then for that l and all subsequent l (since window only shrinks) condition will never be satisfied, so we can break? Actually after r = n and good == 0, we exit while. Then if good == 0, we don't add anything. Then we remove a[l] (which may affect good? But good is 0, so removal can't make good negative? Actually if good=0, then no value has count >=k. Removing a[l] could still keep good=0. But note: after removal, window becomes [l+1, n] which is smaller. Could it become good? No, because if the full window from l to n didn't satisfy condition, a subwindow of that (by removing left) cannot introduce new frequencies; frequencies only decrease, so it cannot become good. So indeed after r reaches n and good=0, all remaining l will also have good=0. We could break out of loop. But not necessary as we can still iterate l up to n; each iteration will do O(1) removal and check, but good stays 0. That's okay, O(n). So overall O(n).
But we must be careful about map overhead: we use unordered_map with many operations. n up to 4e5, and total operations: each index added once, removed once. So about 2n map operations. Unordered_map should be fine, but there is risk of collisions. Could use a vector after compressing values. Since a_i up to 1e9, we can compress: sort distinct values, map to indices 0..m-1. Then use array for frequencies. That would be faster and avoid hashing issues. But unordered_map likely passes. However with n=4e5, unordered_map is okay. But we can do compression for safety.
Now we also need to use 64-bit integer for answer: max subarrays n*(n+1)/2 ~ 8e10 (n=4e5 => 8e10) fits in 64-bit.
Now implement.
Edge Cases: k > n? Actually given k ≤ n, so fine.
The algorithm:
long long solve(): read n, k read array a (0-indexed or 1-indexed) compress: vector b = compress(a) or use unordered_map.
But with unordered_map: unordered_map<int, int> freq; int good = 0; long long ans = 0; int r = 0; for (int l = 0; l < n; l++) { while (r < n && good == 0) { freq[a[r]]++; if (freq[a[r]] == k) good++; r++; } if (good > 0) { ans += n - r + 1; } // remove a[l] if (freq[a[l]] == k) good--; freq[a[l]]--; } cout << ans;
But careful about order: In while loop we increment r before checking? Typically we do: while (r < n && good == 0) { freq[a[r]]++; if (freq[a[r]] == k) good++; r++; } But this increments r after adding. That's fine, but after loop, r is one past the last index we added? Let's re-evaluate.
We start with r = 0, representing next to add? Better to define r as the right bound inclusive. Usually two-pointer: maintain window [l, r] inclusive. Initialize l=1, r=0 empty. Then while r < n and condition not satisfied: r++; update. So after that, window is [l, r] inclusive, with condition satisfied (if r <= n). Then ans += n - r + 1. Then remove a[l] and increment l.
In code using 0-indexed arrays, we can set l=0, r=-1. Then while r+1 < n && good == 0: r++; freq[a[r]]++; if (freq[a[r]] == k) good++. Then after loop, if good>0: ans += n - r. Because subarrays start at l, right endpoints from r to n-1 inclusive: count = n-1 - r + 1 = n - r. For 1-indexed it's n - r + 1. So careful with indices.
Better to use 0-index and adjust:
int l = 0, r = -1; while (l < n) { while (r+1 < n && good == 0) { r++; freq[a[r]]++; if (freq[a[r]] == k) good++; } if (good > 0) { ans += n - r; // because valid r... n-1 inclusive } // remove a[l] if (freq[a[l]] == k) good--; freq[a[l]]--; l++; }
But when r reaches n-1 and good still 0, then after while loop r = n-1 (since r+1 < n false, loop exits). Then good==0, so we don't add ans. Then remove a[l] and continue. That works.
But check: after removal, we increment l. However, note that if r is at n-1 and good==0, then after removing a[l] and increasing l, r remains same; but the window is [l+1, r] which is a subwindow of previous window that also didn't satisfy condition, so good stays 0. So subsequent loops will not enter while (since r+1 < n is false) and good remains 0, so no ans. That's fine.
Now verify with examples using 0-index:
Example1: n=4, k=2, a=[1,2,1,2], indices 0..3. Initialize l=0, r=-1, good=0, ans=0. l=0: while r+1<4 && good==0: r=0: freq[1]=1, not k -> good=0. r=1: freq[2]=1, good=0. r=2: freq[1]=2 -> freq[1]==k? yes, good=1. Now good>0, ans += n - r = 4 - 2 = 2. removal: freq[1] == k? yes -> good-- =>0; freq[1]-- =>1. l=1. l=1: while r+1<4 && good==0: r=3 (since r=2, r+1=3<4): freq[2]++ => freq[2]=2 -> freq[2]==k? yes -> good=1. r=3. ans += n - r = 4 - 3 = 1 => ans=3. removal: freq[2] == k? yes -> good-- =>0; freq[2]-- =>1. l=2. l=2: while r+1<4 && good==0: r+1=4 not <4, so skip. good=0 -> no ans. removal: freq[1] currently 1? Actually freq[1] is 1; freq[1] == k? no; freq[1]-- =>0. l=3. l=3: while ... skip. no ans. removal: freq[2]-- =>0. done. ans=3. Works.
Example2: n=5,k=3,a=[1,2,1,1,3] 0-index. l=0,r=-1. while: add r=0: f1=1; r=1: f2=1; r=2: f1=2; r=3: f1=3 -> good=1; r=3. ans += 5-3=2. remove a[0]=1: f1==k? yes good-- =>0; f1-- =>2. l=1. while: r+1=4<5: r=4: f3=1 -> good=0, r=4 now. r+1=5 not <5, exit. good=0 -> no ans. remove a[1]=2: f2==k? no; f2-- =>0. l=2. while: r+1=5 not <5 -> skip; good=0 -> no ans. remove a[2]=1: f1=2? Actually f1 after removal: f1=2; f1==k? no; f1-- =>1. l=3. similar. ans=2. Works.
Example3: n=3,k=1. l=0,r=-1. while: r=0: f1=1 -> freq==k -> good=1. r=0. ans += 3-0=3. remove a[0]: f1==k? yes good-- =>0; f1-- =>0. l=1. while: r+1=1<3: r=1: f1=1 -> good=1. ans += 3-1=2 => total 5. remove a[1]: f1==k? yes good--; f1--=0. l=2. while: r+1=2<3: r=2: f1=1 -> good=1. ans+=3-2=1 => total6. remove a[2]: good--; f1=0. done. ans=6.
So algorithm correct.
Now time complexity: O(n) with unordered_map. However we must be careful: unordered_map may be slow if we use many operations and we have to handle possible hash collisions. Better to compress values to O(n) distinct values and use vector freq(m). Since n up to 4e5, compression is easy: copy array to vector, sort unique, map each value to index.
So plan:
- read n, k
- read array a (size n)
- create vector b = a
- sort(b.begin(), b.end())
- auto it = unique(b.begin(), b.end())
- b.resize(it - b.begin())
- map each a[i] to compressed index: for i from 0 to n-1: a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() (or create new array comp)
- Now have compressed values in range [0, m-1] where m <= n.
- use vector freq(m, 0)
- then run two pointers.
Implementation details:
We'll need freq size m. For each step when we add a[r], we get idx = a[r], freq[idx]++. If freq[idx] == k: good++. When we remove a[l], idx = a[l]; if freq[idx] == k: good--; freq[idx]--.
Note: Good may count distinct values with freq >= k. But if a value appears many times and we increment from k to k+1, good unchanged; decrement from k+1 to k: that still meets condition, so we should not decrement good then. But careful: when decrementing from k+1 to k, the value still qualifies, so good should not change. Our removal condition (if freq[idx] == k) before decrement? Let's reason: In removal, we have current freq count for idx. After removal, it becomes freq-1. The value will still be >=k if before removal freq >= k+1. If before removal freq == k, after removal it becomes k-1, thus it's no longer >=k, so good--. If before removal freq < k, after removal still <k, good unchanged. If before removal freq > k, after removal >= k, good unchanged. So we need to check if freq[idx] == k before decrement, then good--. That's what we did. In increment, we need to check if after increment freq becomes k, then good++. That's also correct. So we must be careful with ordering.
Now edge: When k=1, increments: freq becomes 1 => good++. That's correct.
Potential bug: The good variable counts number of distinct values with freq >= k. It is possible that multiple values become >=k. In such case, good > 0, and we can still add contributions. But when we remove an element from a value that has freq == k, we decrement good. But what if there are two distinct values both >=k? Then good would be at least 2. Removing one from one value with freq == k will reduce good by 1, but good may still be >0, so condition still holds. This is correct. When we expand r, we may add more values, and if they become k, we increment good. So all good.
Thus algorithm yields number of subarrays where there exists at least one value with count >=k.
Now complexity O(n). Memory O(n) with compression.
Now let's test more cases:
-
All elements distinct, k>1. Then no subarray qualifies. So answer should be 0. Our algorithm: For each l, we try to expand r until good>0. Since all distinct, we will never get any freq >= k (since k>=2). So r will go to n-1 and good=0; no ans. Then removal steps will keep good=0. So ans=0. Works.
-
n=5, k=2, a = [1,1,1,1,1]. For each l, minimal r such that at least 2 of same? Actually since all 1, any subarray of length >=2 qualifies. Number of subarrays total = 15. Subarrays length 1 = 5, which do not qualify (since need at least 2 equal? Actually if k=2, need at least 2 equal numbers; length1 has frequency 1, not >=2). So valid subarrays = total - subarrays of length 1 = 15-5=10. Let's see algorithm:
n=5,k=2. l=0: r expands until good>0: at r=1: freq[0] becomes 2? Actually a[0]=1, a[1]=1. After adding r=0: freq=1, good=0; then r=1: freq=2 => good=1. So r=1. ans += n - r = 5 - 1 = 4 (subarrays: [0..1], [0..2], [0..3], [0..4]) -> count 4. remove a[0]: freq[0]==k? before removal freq=2 ==k => good-- =>0; freq-- =>1. l=1: while good==0 and r+1<5: r=2: freq becomes 2 => good=1. r=2. ans += 5-2=3 => total 7. remove a[1]: before removal freq=2 => good-- =>0; freq-- =>1. l=2: while: r=3: freq=2 => good=1; r=3; ans += 5-3=2 => total 9. remove a[2]: good-- etc. l=3: while: r=4: freq=2 => good=1; r=4; ans += 5-4=1 => total 10. remove a[3]: good--, freq-- =>1. l=4: while: r+1=5 not <5, good=0 => no ans. total 10. Works.
So algorithm works.
Now we must be careful about integer overflow: ans can be up to n*(n+1)/2 ≈ 8e10 for n=4e5, fits in 64-bit.
Now we need to implement reading input and output. Use scanf/printf for speed maybe, but C++ cin with sync_with_stdio(false) is okay. We'll use faster I/O.
Edge Cases: The array may have large values, but compression works.
Potential pitfalls:
- In removal step, after we remove a[l], we then increment l. But what about the case where r is less than l? That never happens because we always have r >= l-1? Actually initially r = -1, l=0, r<l, but we immediately expand r. When we remove element and increment l, if l becomes > r, then we have an empty window. But that can happen? For example, if after removal l becomes greater than r? Suppose at some step, we had window [l, r] where l == r (single element). If condition good may be 1 if k=1. Then after removal, we decrement freq and good, then increment l, now l = r+1. At that point, before next loop, we have l > r, and window effectively empty. In the next iteration, the while condition checks r+1 < n && good == 0. Since good is 0, we will expand r from its current value (which is less than l) to l. But we must ensure that the frequencies are correctly representing the window. When we have empty window, frequencies should be zero. However after removal we have decremented freq. But after we increment l, we haven't updated r. Suppose before removal: window = [i, i] with freq count 1. After removal: we decrement freq for a[i]; now freq for that value becomes 0. Then we increment l to i+1. Now r is still i. So the window is effectively [i+1, i] empty. But our freq map is all zero? Yes, because we removed the only element. So it's consistent: freq counts for elements in window [l, r] inclusive. However r < l indicates window empty, but our freq map is zero because we removed all. When we go into while loop, we will expand r starting from r+1 (which is i+1) to add new elements. So it's fine.
But there is a nuance: after removal, if the element we removed was the one that made good>0, we decrement good. So good becomes 0. In next iteration, while loop condition good==0 true, so we will expand r until good>0 or r reaches end. That is correct.
Now about the good variable: It counts distinct values that have freq >= k. But what about the possibility of a value's frequency dropping from >k to k? That doesn't affect good because it was already counted; after decrement it's still >=k, so good unchanged. However if we decrement from k+1 to k, and we had previously incremented good when it first reached k, good stays at 1. That's correct. The only time good decreases is when freq goes from exactly k to k-1.
But could it happen that a value's freq goes from k+? to something still >=k, but we need to track if there are multiple values? Already good counts distinct values. Suppose we have two values each with freq >= k. good = 2. If we remove from one value, its freq may drop from k to k-1, then good becomes 1. If it drops from k+1 to k, good remains 2. That's fine.
Implementation details:
We'll compress: vector values(a.begin(), a.end()); sort(values.begin(), values.end()); values.erase(unique(values.begin(), values.end()), values.end()); for (int i = 0; i < n; i++) { int idx = lower_bound(values.begin(), values.end(), a[i]) - values.begin(); a[i] = idx; } int m = values.size(); vector freq(m, 0);
Then run two-pointer as described.
But careful: using lower_bound for each a[i] after sorting and unique, we need the original a values before overwriting. So we might make a copy.
Alternative: read into vector arr(n); then create copy comp = arr; then sort unique, then map each arr[i] to compressed index, perhaps using unordered_map for mapping but that defeats compression. So better: after sorting unique, we can use an unordered_map from original value to index. That would be O(n) average but still uses hash. But we can use binary search per element O(n log n) which is fine. n=4e5, log n ~19, so fine.
We'll do:
vector b(a); sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); unordered_map<int, int> comp; // or use vector and lower_bound. for (int i = 0; i < b.size(); i++) comp[b[i]] = i; for (int i = 0; i < n; i++) a[i] = comp[a[i]];
But that uses unordered_map but size small (<=n). That's fine. Or we could just use binary search without map: for each a[i], idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin(); That's O(n log m) which is okay; m <= n.
Given n=4e5, O(n log n) is fine.
Now ensure we use long long for ans.
Potential integer overflow: n-r, where r may be -1? In while loop before any expansion, if initially r = -1, we might try to add ans? But we only add if good>0, and good can only be >0 after we have added at least one element and freq >= k. Since initially r = -1, good=0, we won't add. So ans safe.
Now check scenario: k=0? But constraints say k>=1.
Now confirm that the algorithm counts each subarray exactly once. For each left index l, we find minimal r such that condition holds. Then any extension to the right also holds. So each subarray is counted exactly once by its left endpoint. Because for a given subarray (l, r'), it will be counted when left index = l and minimal r is the smallest r such that condition holds, and since r' >= r, it will be included. So it's correct.
Now we must consider that condition could be satisfied at multiple minimal r for a given l? Actually minimal r is unique. So counting method correct.
Now we need to ensure that we handle the case where condition is never satisfied for a given l. Then we don't add anything and eventually break after r reaches n-1 and good remains 0. That's correct.
Time Complexity: O(n) after compression (or O(n log n) with binary search compression). Both fine.
Now let's test with random cases to be sure.
We'll write some small brute force to verify for random arrays small n to ensure algorithm matches.
But before coding, think about possible pitfalls: The good variable could become negative if we decrement incorrectly. We must ensure the condition: if freq[idx] == k before decrement, then good--. That's fine. But consider when we remove element from window that was not part of window? Not possible.
Now what about integer overflow in ans addition: n - r may be large; but we use long long.
Now memory: freq vector of size up to 4e5, fine.
Now implement.
But note: The while loop condition "while (r+1 < n && good == 0)" might cause r to be incremented even if good becomes >0 within loop, but after increment we check condition again? In our while loop, we increment r first, then update freq and good. So after each addition, we check condition (good == 0) to decide whether to continue. But careful: we must check after updating freq and before loop condition? The typical pattern:
while (r < n && good == 0) { r++; freq[a[r]]++; if (freq[a[r]] == k) good++; }
But if we start with r = -1, we need to make sure a[r] indexing correct. Better to do:
while (r+1 < n && good == 0) { r++; freq[a[r]]++; if (freq[a[r]] == k) good++; }
That is safe.
Alternatively:
for (int l=0, r=-1; l<n; l++) { while (r+1 < n && good == 0) { r++; freq[a[r]]++; if (freq[a[r]] == k) good++; } if (good > 0) ans += n - r; // remove a[l] if (freq[a[l]] == k) good--; freq[a[l]]--; }
Make sure to use long long for ans.
Now test with a case: n=1,k=1,a=[5]. Should output 1. Simulate: l=0, r=-1, while good==0 and r+1<1 => r=0: freq[5]=1, good++ (since k=1). ans += n - r = 1-0=1. removal: freq[5]==k? yes, good--, freq--=0. done. ans=1.
n=1,k=2 => 0. Simulate: l=0, while good==0 and r+1<1: r=0, freq=1, not k, good=0. loop condition false (r+1<1 now false). good=0, no ans. removal: freq[5]==k? no, freq-- =>0. ans=0. correct.
Now test with n=5,k=2,a=[1,2,3,1,1]. Subarrays with at least two 1s? Actually condition: any subarray that contains at least 2 equal numbers. Which values appear multiple times? 1 appears three times at indices 0,3,4. 2 appears once,3 once. So subarrays that have at least two 1s are those containing at least two of indices {0,3,4}. Also any other value? No. So count manually? Let's compute using brute mental: Subarrays: [0-0] no [0-1] (1,2) no [0-2] (1,2,3) no [0-3] (1,2,3,1) yes (two 1s) [0-4] (1,2,3,1,1) yes (three 1s) [1-1] (2) no [1-2] (2,3) no [1-3] (2,3,1) no [1-4] (2,3,1,1) yes (two 1s) [2-2] (3) no [2-3] (3,1) no [2-4] (3,1,1) yes (two 1s) [3-3] (1) no [3-4] (1,1) yes [4-4] (1) no Total = ?: [0-3],[0-4],[1-4],[2-4],[3-4] => 5. So answer should be 5.
Now run algorithm: compress: values 1,2,3 -> indices 0,1,2. n=5,k=2. l=0,r=-1,good=0. while: r=0: freq[0]=1, good=0. r=1: freq[1]=1, good=0. r=2: freq[2]=1, good=0. r=3: freq[0]=2 -> freq[0]==k? yes -> good=1. r=3. ans += 5-3=2 (subarrays [0-3],[0-4]) remove a[0] (0): freq[0]==k? yes (2) -> good-- =>0; freq[0]-- =>1. l=1. while good==0 and r+1<5: r=4: freq[0]++ =>2 -> good=1. r=4. ans += 5-4=1 => total 3. remove a[1] (1): freq[1]==k? no (1), good unchanged; freq[1]-- =>0. l=2. while good==0? currently good=1 (since freq[0]=2) so skip while. ans += 5 - r = 5-4=1 => total 4. remove a[2] (2): freq[2]==k? no; freq[2]-- =>0. l=3. while good==0? good currently 1? Wait after removal of a[2], we haven't changed good because freq[2] was 1 before decrement. But check: after removal of a[2], freq[2] becomes 0, good still 1 because freq[0]=2. So good>0. So ans += 5 - r = 5-4=1 => total 5. remove a[3] (0): freq[0]==k? yes (2) -> good-- =>0; freq[0]-- =>1. l=4. while good==0 and r+1<5? r=4, r+1=5 not <5, skip. good=0 no ans. remove a[4] (0): freq[0]==k? no (1) -> freq[0]-- =>0. done ans=5. Works.
Now test another: n=5, k=2, a=[1,2,1,2,3]. Subarrays with at least two equal numbers? Let's list: 1 appears at indices 0,2; 2 appears at 1,3. So subarrays containing at least two 1s or two 2s. Need to count. We'll simulate quickly:
Using algorithm: l=0,r=-1: expand until good>0: r=0 f1=1 r=1 f2=1 r=2 f1=2 -> good=1, r=2. ans += 5-2=3? n=5, r=2 -> n-r = 3? Actually n=5, index 0..4, r=2 -> n - r = 3? That would be count of subarrays starting at l=0 with right endpoint 2..4 => [0-2],[0-3],[0-4] = 3. But check: [0-2] = (1,2,1) qualifies (two 1s). [0-3] = (1,2,1,2) qualifies (two 1s? Actually has two 1s and two 2s, yes). [0-4] = (1,2,1,2,3) qualifies (two 1s). So 3. Now remove a[0]: freq1 was 2 => good-- =>0; freq1->1. l=1: window [1,2] (indices 1-2): values (2,1) frequencies: 1:1,2:1, good=0. while good==0: r=3: freq2 becomes 2? Actually a[3]=2, freq2=2 -> good=1. r=3. ans += 5-3=2 (subarrays starting at 1 with right endpoint 3..4: [1-3] = (2,1,2) qualifies (two 2s), [1-4] = (2,1,2,3) qualifies) total ans=5. remove a[1]=2: freq2==k? yes (2) -> good-- =>0; freq2->1. l=2: window [2,3] indices 2-3: (1,2) frequencies: 1:1,2:1 good=0. while good==0: r=4: a[4]=3, freq3=1 -> good still 0. r=4, still good=0, and r+1=5 not <5, loop ends. good=0 => no ans. remove a[2]=1: freq1==k? no (1) -> freq1->0. l=3: window [3,4] indices 3-4: (2,3) freq2=1, freq3=1 good=0. r=4 already, so no ans. remove a[3]=2: freq2==k? no -> freq2->0. l=4: window [4,4]: (3) freq3=1 good=0, no ans. Total ans=5. Let's brute force: subarrays with at least 2 equal numbers: [0-2], [0-3], [0-4], [1-3], [1-4] -> that's 5. Also maybe [2-?] Actually [2-?] doesn't have two 1s? [2-4] = (1,2,3) has only one 1, one 2, one 3. [2-?] also no. [3-?] none. So 5. Good.
Now test scenario where multiple distinct values reach k. For example, n=6, k=2, a=[1,1,2,2,3,3]. All values appear twice. Subarrays that have at least one value appearing at least twice: essentially any subarray that includes both occurrences of any value. But many subarrays will satisfy condition if they include at least two of the same number. Let's compute algorithm's output. We'll trust.
But let's verify logic: Good counts distinct values with freq >= k. When we have both 1 and 2 with freq>=2, good=2. Then we remove leftmost, maybe good stays >0, we still count contributions. That's fine.
Now about the "at least k equal numbers" condition: It says at least k equal numbers. That's exactly our condition (exists value with frequency >= k). So algorithm solves.
But wait: Could there be a scenario where the minimal r for a given l is not the first time any value reaches k? Suppose that before reaching k for some value, the window already satisfies because of a different value? Actually we are looking for any value reaching k. The minimal r is indeed the first index where after adding a[r] we have some freq >= k. So that's correct.
Thus solution is correct.
Now we need to output answer as a 64-bit integer. In C++ we can use long long and cout.
Now about time: The two-pointer loop is O(n). The compression step O(n log n). With n=4e5, it's fine.
But we should be careful about using unordered_map for compression: might be okay, but lower_bound is also fine. I'll use sort and binary search for each element: for (int &x : a) x = lower_bound(b.begin(), b.end(), x) - b.begin(); This is O(n log n). n=4e5 => 4e5 * log2(4e5) ≈ 4e5 * 19 = 7.6e6, fine.
Now we need to avoid using recursion.
Now note: The two-pointer algorithm counts subarrays correctly. But is there any scenario where the condition holds for a given l but the minimal r is not found correctly due to good variable? Because good>0 as soon as any value reaches k. So as we expand r, good becomes >0 exactly when the first value reaches k, because before that, no value has freq >= k, so good=0. So that yields minimal r.
But consider case where multiple values simultaneously reach k at same index? That's impossible because only one value's count increments each step. So fine.
Now edge: When we remove a[l] that caused good to become 0, but there could be another value with freq >= k still present. That's captured because we only decrement good when freq becomes k-1. If there is another value with freq >= k, good would be at least 1 before removal, and after removal we might still have good >0. In that case we won't decrement good? Wait we decrement good only if freq[a[l]] == k. That only affects the value we are removing. If there is another value with freq >= k, good remains >0, so condition still holds. That's correct.
Now check scenario: Suppose freq[a[l]] > k, then after removal it still >= k, so good unchanged. That is correct.
Thus algorithm robust.
Now one more nuance: The variable good counts distinct values with freq >= k. If we have multiple values meeting condition, good >1. If we remove one that had freq == k, good-- but may still be >=1. So condition still holds. That matches: minimal r for new l may be less than current r? Actually when we remove left element, the window shrinks from [l, r] to [l+1, r]. It's possible that the condition still holds for [l+1, r] even after removal. In that case, the minimal r for l+1 might be <= current r. Our algorithm will not shrink r; it only expands r. So for l+1, the minimal r might be less than current r, but we will not move r leftwards. However, we are not required to find the minimal r exactly; we only need to count the number of subarrays starting at l+1 that satisfy condition. For that, we need the smallest r' such that [l+1, r'] satisfies condition. But if [l+1, r] already satisfies, then the minimal r' is ≤ r. However, if we count ans using the current r, we would add (n - r) for l+1. But that would undercount? Actually we would be adding n - r, but the actual number of valid subarrays starting at l+1 is n - (minimal_r) which is >= n - r. Since our ans uses the current r, which might be larger than minimal_r, we would be adding less than actual count, leading to undercount. Wait, we need to be careful.
Our algorithm as described: For each l, we maintain a window [l, r] such that good > 0, and r is the smallest index such that [l, r] satisfies? Actually we maintain r as the smallest index such that [l, r] satisfies condition? Let's check the invariants.
We start l=0, and we expand r until good>0. At that point, r is the first index where after adding a[r] we got good>0. So for this l, r is indeed minimal. Then we count ans += n - r. Then we remove a[l] and increment l. Now for the new l (l+1), we have window [l+1, r] (since we didn't change r). Is r minimal for l+1? Not necessarily. Because after removal, the condition might still be satisfied for [l+1, r]. That means the minimal r' for l+1 could be less than or equal to r. But we are using the same r to compute ans for l+1 (if good>0). However, if r is not minimal for l+1, then using r will give ans += n - r, but the true number of valid subarrays for l+1 is n - (minimal_r'), which is larger because minimal_r' ≤ r. Thus we would be undercounting.
But wait, in our earlier simulation, we saw that after removal, good might become 0, in which case we need to expand r again. But what if good remains >0? Then we would add ans for l+1 using the current r, which might be larger than minimal. But is it possible that after removal, condition still holds, and r is not minimal? Example: Consider array where there are multiple values satisfying condition. For left index l, minimal r is some position. When we move to l+1, the window might still satisfy condition even though we removed an element. Then the minimal r for l+1 could be less than or equal to current r. But since we never move r leftwards, our r is not minimal. However, we are counting ans as n - r. But if minimal r' is less than r, then the true number of subarrays for l+1 is n - r' + 1? Actually careful: For a given left index L, we need to count number of right indices R >= L such that subarray [L,R] satisfies condition. If the minimal R that satisfies is R_min, then all R >= R_min also satisfy, so count = n - R_min (in 0-index) if we consider R from R_min to n-1 inclusive: count = n - R_min. If we use a larger value R' > R_min, then n - R' would be smaller, thus undercounting.
So indeed, if we use a non-minimal r, we undercount.
But does our algorithm produce correct results? Let's test with a scenario where after removal good remains >0. Example: n=6, k=2, a = [1,1,2,2,3,3] maybe? Actually we need a case where for l, minimal r is something, and for l+1, the minimal r is less than that. Let's construct.
Suppose a = [1,1,2,1]? n=4,k=2? Let's test:
a = [1,1,2,1], k=2. Subarrays with at least two equal numbers? Let's list: [0-1]: (1,1) yes [0-2]: (1,1,2) yes (1 appears twice) [0-3]: (1,1,2,1) yes (1 appears three times) [1-2]: (1,2) no? Actually 1 appears once, 2 once => no [1-3]: (1,2,1) yes (1 appears twice) [2-3]: (2,1) no So total valid subarrays: [0-1],[0-2],[0-3],[1-3] => 4.
Now run algorithm:
Initialize l=0, r=-1, good=0. while good==0: r=0: freq1=1 r=1: freq1=2 => good=1, r=1 ans += n - r = 4 - 1 = 3 (subarrays [0-1],[0-2],[0-3]) remove a[0]=1: before removal freq1=2 ==k => good-- =>0; freq1=1. Now l=1, window [1,1]? Actually r=1, so window indices 1..1? But we removed a[0], so elements in window are only index 1? freq currently: a[1]=1 count 1, a[?] Wait after removal: we decremented freq1 from 2 to 1, and we have not added anything else. So window is [1,1] (since l=1, r=1) containing a[1]=1. That's correct. good=0. Now while good==0 and r+1<n: r=2: freq2=1 => good=0 r=3: a[3]=1, freq1 becomes 2 => good=1, r=3. ans += n - r = 4 - 3 = 1 => total 4. remove a[1]=1: before removal freq1=2 ==k => good-- =>0; freq1=1. l=2, window [2,3] (indices 2,3) with a[2]=2 count1, a[3]=1 count1 => good=0. while good==0 and r+1<n: r=4? r=3, r+1=4 not <4, so skip. good=0 no ans. remove a[2]=2: freq2==k? no; freq2-- =>0. l=3, window [3,3] with a[3]=1 count1 => good=0, no ans. Total ans=4, correct.
In this example, after removal at l=0, good became 0, so we expanded r. So we didn't have case where good remained >0.
Let's find a case where after removal, good remains >0. That requires that after removing leftmost element, there is still some value with frequency >= k. That means that there is another value (or same value with count > k) that still meets condition.
Example: a = [1,2,1,1] with k=2. Let's compute: Subarrays: [0-2] (1,2,1) yes (two 1s) [0-3] (1,2,1,1) yes (three 1s) [1-?] (2,1,1) [1-3] yes (two 1s) [2-3] (1,1) yes [0-1]? (1,2) no [1-2]? (2,1) no [2-?]? [2-2]? no [3-3]? no Thus total: [0-2],[0-3],[1-3],[2-3] = 4.
Now algorithm:
l=0,r=-1,good=0. while good==0: r=0: f1=1 r=1: f2=1 r=2: f1=2 -> good=1, r=2. ans += n - r = 4 - 2 = 2 (subarrays [0-2],[0-3]) remove a[0]=1: before removal f1=2 ==k => good-- =>0; f1=1. Now window [1,2] (indices 1-2): values (2,1) freqs: f1=1,f2=1, good=0. while good==0: r=3: a[3]=1, f1=2 -> good=1, r=3. ans += n - r = 4-3 =1 => total 3. remove a[1]=2: before removal f2=1 < k => good unchanged; f2=0. Now l=2, window [2,3] (1,1) f1=2, good=1 (since f1=2 >=k). So good>0. ans += n - r = 4 - 3 = 1 => total 4. remove a[2]=1: before removal f1=2 ==k => good-- =>0; f1=1. l=3, window [3,3] f1=1 good=0, no ans. Total 4, correct.
Here after removal at l=1, good remained >0? Actually at l=1 removal, before removal good was 1? Let's see: At l=2 step, before removal at l=1, we had window [1,3]? Wait check carefully: after l=1 removal, we went to l=2, and before removal we had computed ans for l=2. At that point, we had good>0 (window [2,3]) and we added ans. Then we removed a[2] making good 0. So in this example, we did have a case where after removal (from l=1 to l=2) the condition still held. However note that r at that point was 3. The minimal r for l=2 is? For left index 2, subarray starting at index2: [2,2] = (1) not good; [2,3] = (1,1) good, so minimal r=3. So r=3 is indeed minimal. So we used r=3 and added n - 3 = 1, correct.
Now try to construct a case where after removal, good remains >0 and current r is larger than minimal r for new l. That would mean that for left index l+1, the minimal r' is less than current r, but we still have good>0 with current r. How could that happen? For good>0 to hold, we need some value with freq >= k in the current window [l+1, r]. The minimal r' is the smallest index such that [l+1, r'] satisfies. Since [l+1, r] satisfies, r' ≤ r. It could be that r' < r. For r' < r, it means that we could shrink the window on the right and still have condition satisfied. But would that be possible? If we shrink the window by moving r leftwards, we would remove elements from the right. That could reduce frequencies. Could it be that after moving r leftwards, condition still holds? That would mean there is a smaller suffix of the window that already meets condition. But note that our window [l+1, r] is a subarray that satisfies condition. The minimal r' for l+1 is the smallest index >= l+1 such that subarray [l+1, r'] satisfies. Since r' is minimal, it must be that for any index < r' the condition fails. So if r' < r, then the window [l+1, r] is larger than necessary; but if we remove some elements from the right (making it [l+1, r-1]), condition might still hold if the frequencies of the value that cause condition are still >= k even after removing some rightmost elements. For that to happen, the elements we remove from the right must not include the value that triggers the condition, or if they do, its count remains >= k. Could that cause r' < r? Let's think: Suppose we have left index L = l+1. The minimal R is the first time we have some value's count reach k as we expand from L to the right. So at R, that value's count becomes exactly k. After that, if we include more elements, its count may increase or other values may also reach k. Now if we then remove left element from original window, we get new left index L+1 and we keep the same right boundary r (which is > minimal R for the original L). But is it possible that for new L, the minimal R' is less than r? Let's examine.
We have original window [l, r] where condition holds. Minimal r for l is some value, call r_min_l. When we increment l to l+1, we remove a[l]. If after removal, condition still holds, it means that there is some value whose frequency in [l+1, r] is >= k. The minimal r for l+1 would be the smallest index R' such that [l+1, R'] has freq >= k. Since [l+1, r] already has that property, R' ≤ r. Could R' be < r? Yes, if the condition was already satisfied at some earlier point within [l+1, r] before reaching r. But note that r_min_l was the first index where condition became true for starting index l. For starting index l+1, the condition might become true at an index ≤ r. However, r could be larger than that.
Consider a case: a = [1, 2, 1, 1, 2] with k=