d2p2 — CCO Canadian_Computing_Olympiad
Task type: batch | Time limit: 4 s | Memory limit: 1024 MB | Difficulty: 22
Algorithms: line sweep, data structures, segment tree, dynamic programming

## 2024 Canadian Computing Olympiad

### Day 2, Problem 2: Heavy Light Decomposition

**Time Limit:** 4 seconds

#### Problem Description

In an array containing only positive integers, we say an integer is heavy if it appears more than once in the array, and light otherwise.

An array is good if the integers in the array alternate between light and heavy.

Given an array $a_1, \dots, a_N$, count the number of ways to partition it into some number of contiguous subarrays such that each subarray, when considered as an array on its own, is good. As the answer may be large, output it modulo 1\,000\,003.

#### Input Specification

The first line of input contains a single integer, $N$.

The next line contains $N$ integers $a_1, \dots, a_N$ ($1 \le a_i \le N$).

| Marks Awarded | Bounds on $N$          | Additional Constraints                         |
|---------------|------------------------|------------------------------------------------|
| 3 marks       | $2 \le N \le 50\,000$  | For each $i$, $a_i \le 26$.                  |
| 4 marks       | $2 \le N \le 5\,000$   | No additional constraints.                     |
| 5 marks       | $2 \le N \le 500\,000$ | If $i$ is odd, then $a_i = 1$.                |
| 6 marks       | $2 \le N \le 500\,000$ | Any number appears at most twice in the array. |
| 7 marks       | $2 \le N \le 500\,000$ | No additional constraints.                     |

#### Output Specification

The number of ways to partition the array into good contiguous subarrays, modulo 1\,000\,003.

#### Sample Input 1

```
5
1 2 3 2 3
```

**Output for Sample Input 1:**
```
4
```

#### Explanation of Output for Sample Input 1

There are four valid partitions of $[1, 2, 3, 2, 3]$:

*   $[1], [2], [3], [2], [3]$
*   $[1], [2, 3, 2], [3]$
*   $[1], [2], [3, 2, 3]$
*   $[1, 2, 3, 2], [3]$

#### Sample Input 2

```
5
1 2 1 3 1
```

**Output for Sample Input 2:**
```
6

Starter code: