Temirulan vs. Pernekhan#7797
Temirulan and Pernekhan have been given a sequence consisting of (1 \leq n \leq 5000) positive integers. They have decided to divide this sequence between them. Each of them must select a non-empty contiguous segment of the sequence, with Temirulan's segment coming before Pernekhan's. To ensure uniqueness, they want no integer to appear in both segments at the same time. Aidos, who is observing, is curious about the number of different ways they can achieve this division. Your task is to write a program that calculates the number of possible ways.
The first line contains the integer . The second line contains integers A_i (1 \leq A_i \leq n, 1 \leq i \leq n), separated by spaces.
Print a single integer representing the number of ways to split the sequence according to the rules.
Example 1
Example 2
Example 3
In the second test case, the sequence can be split in the following ways:
{ [] [] }, { [] [] }, { [] [] },
{ [] [] }, { [] [] }, { [] [] },
{ [] [] }, { [] [] }, { [] [] }