Set of three numbers - MarisaOJ: Marisa Online Judge

Given a sequence of positive integers

$a_1, a_2, \ldots, a_n$ , a triplet

$(i, j, k)$ is called a "beautiful triplet" if it satisfies the following conditions: -

$1 \leq i < j < k \leq n$ . - Define the consecutive subsequence

$a_i, a_{i+1}, \ldots, a_j$ as

$A$ and the consecutive subsequence

$a_j, a_{j+1}, \ldots, a_k$ as

$B$ . The subsequences

$A$ and

$B$ satisfy: - Every value that appears in

$A$ also appears in

$B$ . - Every value that appears in

$B$ also appears in

$A$ . **Objective**: Given the sequence

$a$ , count the number of beautiful triplets

$(i, j, k)$ in the sequence. #### Input - The first line contains an integer

$n$ (

$1 \leq n \leq 10^5$ ). - The second line contains

$n$ integers

$a_1, a_2, \ldots, a_n$ (

$1 \leq a_i \leq 10^6$ ). #### Output - Output a single integer, which is the number of beautiful triplets in the given sequence. #### Example Input:

$7 3 1 2 1 2 3 1$

Output:

$4$

Explanation: The valid beautiful triplets

$(i, j, k)$ are: 1.

$(1, 3, 5)$ 2.

$(1, 4, 6)$ 3.

$(2, 4, 6)$ 4.

$(3, 5, 7)$ #### Subtasks - **Subtask 1 (20 points)**:

$n \leq 100$ . - **Subtask 2 (20 points)**:

$n \leq 1000$ . - **Subtask 3 (20 points)**:

$n \leq 10^4$ . - **Subtask 4 (20 points)**: Each value appears exactly twice. - **Subtask 5 (20 points)**: No additional constraints.

Topic

Others

Rating

2000

Solution (0)

Solution