Taco Partitioning

You are given an array of length \(n\) consisting of integers that can only be \(1\), \(2\), or \(3\). Your task is to partition this array into the minimum number of contiguous subarrays such that each subarray contains exactly one occurrence of each of the numbers \(1\), \(2\), and \(3\).

The problem requires determining how many contiguous segments you can extract where every segment has exactly one \(1\), one \(2\) and one \(3\). A greedy strategy is employed: for each segment, consider the earliest occurrence of each number available and form the segment that ends at the maximum of these indices, then remove all elements up to that index from further consideration.

inputFormat

Input Format:

The first line contains an integer \(n\) (with \(n \ge 3\)), the length of the array. The second line contains \(n\) space-separated integers. Each integer is either \(1\), \(2\), or \(3\).

outputFormat

Output Format:

Output a single integer representing the minimum number of contiguous subarrays into which the array can be partitioned, so that each subarray contains exactly one occurrence of \(1\), \(2\), and \(3\).

7
1 3 2 3 1 2 1

2