A shelf holds n products in a row, each given by a product id. Let D be the number of distinct product ids on the whole shelf. Count how many contiguous subarrays contain all D distinct ids (a complete subarray). Distinct index ranges are counted separately.
Line 1: an integer n.
Line 2: n space-separated integers, the product ids in order.
A single integer: the number of complete contiguous subarrays.
Example 1
Input
4 1 2 1 3
Expected
2
Explanation
The shelf has 3 distinct ids {1,2,3}. Only [1 2 1 3] and [2 1 3] contain all three, so the count is 2.
Example 2
Input
3 5 5 5
Expected
6
Explanation
There is a single distinct id, so every one of the 6 subarrays is complete.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →