codeforces#P1284B. New Year and Ascent Sequence
New Year and Ascent Sequence
Description
A sequence of length has an ascent if there exists a pair of indices such that and . For example, the sequence has an ascent because of the pair , but the sequence doesn't have an ascent.
Let's call a concatenation of sequences and the sequence that is obtained by writing down sequences and one right after another without changing the order. For example, the concatenation of the and is the sequence . The concatenation of sequences and is denoted as .
Gyeonggeun thinks that sequences with ascents bring luck. Therefore, he wants to make many such sequences for the new year. Gyeonggeun has sequences which may have different lengths.
Gyeonggeun will consider all pairs of sequences and (), and will check if its concatenation has an ascent. Note that he may select the same sequence twice, and the order of selection matters.
Please count the number of pairs () of sequences whose concatenation contains an ascent.
The first line contains the number () denoting the number of sequences.
The next lines contain the number () denoting the length of , followed by integers () denoting the sequence .
It is guaranteed that the sum of all does not exceed .
Print a single integer, the number of pairs of sequences whose concatenation has an ascent.
Input
The first line contains the number () denoting the number of sequences.
The next lines contain the number () denoting the length of , followed by integers () denoting the sequence .
It is guaranteed that the sum of all does not exceed .
Output
Print a single integer, the number of pairs of sequences whose concatenation has an ascent.
Samples
Note
For the first example, the following arrays have an ascent: . Arrays with the same contents are counted as their occurences.