Colorful Intervals

Interview

Time limit1sMemory limit2048 MB

Summary

Given n painting colors in a line, find two intervals that together contain every color, minimizing the sum of their lengths.

Level: Medium6 of 10
Topics: Sliding window, Array, Hash map
Solved: No attempts yet

Problem

The Museum of Contemporary Art is holding a painting gallery focused on modern art, especially Monochromatic style paintings, which use only a single color. The gallery displays $n$ paintings arranged in a line.

The ICPC wants to bring students on an excursion to the gallery to spark their interest in art. However, the students are programmers, and everyone knows programmers only care about the colors of these modern paintings. They are also somewhat impatient. To keep their attention and to ensure they see every color without overwhelming them, the organizer decided to show them exactly two intervals of paintings. The task is to find two intervals of paintings such that each color appears at least once in at least one of the intervals, and the total number of paintings the students need to see is minimized.

Input

The input consists of a single line containing an integer $n$ ( $2 \le n \le 2000$ ), the number of paintings. This is followed by $n$ lines, each containing a string that is the color of one painting. Each color is a non-empty lowercase string shorter than 20 characters. The input has at least 2 and at most 50 different colors.

Output

Print the minimum number of paintings the students need to see, which is the sum of the lengths of the two intervals.

Examples2

Example 1
Input
```
5
blue
red
blue
black
red
```
Expected output
```
3
```

Example 2

Input

8
peachfuzz
livingcoral
livingcoral
teal
teal
livingcoral
livingcoral
coral

Expected output