Triangles

Interview

Time limit1sMemory limit1024 MB

Summary

Count triples of segments, one of each color, that satisfy the strict triangle inequality on their lengths.

Level: Medium5 of 10
Topics: Sorting, Two pointers, Combinatorics, Binary search
Solved: No attempts yet

Problem

A set of N segments is given. Each segment is defined by a length and a color. The possible colors are blue, green, and red.

Write a program triangle that finds the number of triangles that can be formed from the set of segments such that each triangle contains segments of all three colors.

Input

The first line of the standard input contains a single integer N, the number of segments. Each of the following N lines contains the color and the length of one segment. Colors are given by their first letters: b for blue, g for green, r for red.

Output

Print a single number on one line of the standard output: the number of triangles that can be formed.

Constraints

1 ≤ N ≤ 6000
0 < segment length ≤ 100000

Hint

The three triangles are: {(r 10), (g 10), (b 12)}, {(r 10), (g 6), (b 12)}, {(r 5), (g 10), (b 12)}

Examples1

Example 1
Input
```
5
r 10
g 10
b 12
r 5
g 6
```
Expected output
```
3
```