Cheers
InterviewTime limit2sMemory limit128 MB
Given N people around a circle each drinking a cola brand, find the maximum number of non-crossing pairs connecting people with the same brand.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Intervals
- Solved
- No attempts yet
Problem
N people are sitting around a circular table in clockwise order, and each person is drinking one brand of cola. Two people may form a toast pair only when both conditions below are satisfied.
- The two people are drinking the same brand of cola.
- Among all toast pairs made at the same time, no two pairs' arms may cross.
In the picture, the left arrangement is possible because the connections do not cross, while the right arrangement is not possible. Given N and the cola brand of each person in clockwise order, find the maximum number of toast pairs that can be made at the same time.
Input
The first line contains the number of people N (1 ≤ N ≤ 1000).
The second line contains N integers a_i (1 ≤ a_i ≤ 100), separated by spaces. The integers are given in clockwise order and represent the cola brand each person is drinking.
Output
Print the maximum number of toast pairs that can be made at the same time.