codeforces#P1284B. New Year and Ascent Sequence

    ID: 30796 远端评测题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>binary searchcombinatoricsdata structuresdpimplementationsortings*1400

New Year and Ascent Sequence

Description

A sequence a=[a1,a2,,al]a = [a_1, a_2, \ldots, a_l] of length ll has an ascent if there exists a pair of indices (i,j)(i, j) such that 1i<jl1 \le i < j \le l and ai<aja_i < a_j. For example, the sequence [0,2,0,2,0][0, 2, 0, 2, 0] has an ascent because of the pair (1,4)(1, 4), but the sequence [4,3,3,3,1][4, 3, 3, 3, 1] doesn't have an ascent.

Let's call a concatenation of sequences pp and qq the sequence that is obtained by writing down sequences pp and qq one right after another without changing the order. For example, the concatenation of the [0,2,0,2,0][0, 2, 0, 2, 0] and [4,3,3,3,1][4, 3, 3, 3, 1] is the sequence [0,2,0,2,0,4,3,3,3,1][0, 2, 0, 2, 0, 4, 3, 3, 3, 1]. The concatenation of sequences pp and qq is denoted as p+qp+q.

Gyeonggeun thinks that sequences with ascents bring luck. Therefore, he wants to make many such sequences for the new year. Gyeonggeun has nn sequences s1,s2,,sns_1, s_2, \ldots, s_n which may have different lengths.

Gyeonggeun will consider all n2n^2 pairs of sequences sxs_x and sys_y (1x,yn1 \le x, y \le n), and will check if its concatenation sx+sys_x + s_y has an ascent. Note that he may select the same sequence twice, and the order of selection matters.

Please count the number of pairs (x,yx, y) of sequences s1,s2,,sns_1, s_2, \ldots, s_n whose concatenation sx+sys_x + s_y contains an ascent.

The first line contains the number nn (1n1000001 \le n \le 100\,000) denoting the number of sequences.

The next nn lines contain the number lil_i (1li1 \le l_i) denoting the length of sis_i, followed by lil_i integers si,1,si,2,,si,lis_{i, 1}, s_{i, 2}, \ldots, s_{i, l_i} (0si,j1060 \le s_{i, j} \le 10^6) denoting the sequence sis_i.

It is guaranteed that the sum of all lil_i does not exceed 100000100\,000.

Print a single integer, the number of pairs of sequences whose concatenation has an ascent.

Input

The first line contains the number nn (1n1000001 \le n \le 100\,000) denoting the number of sequences.

The next nn lines contain the number lil_i (1li1 \le l_i) denoting the length of sis_i, followed by lil_i integers si,1,si,2,,si,lis_{i, 1}, s_{i, 2}, \ldots, s_{i, l_i} (0si,j1060 \le s_{i, j} \le 10^6) denoting the sequence sis_i.

It is guaranteed that the sum of all lil_i does not exceed 100000100\,000.

Output

Print a single integer, the number of pairs of sequences whose concatenation has an ascent.

Samples

输入数据 1

5
1 1
1 1
1 2
1 4
1 3

输出数据 1

9

输入数据 2

3
4 2 0 2 0
6 9 9 8 8 7 7
1 6

输出数据 2

7

输入数据 3

10
3 62 24 39
1 17
1 99
1 60
1 64
1 30
2 79 29
2 20 73
2 85 37
1 100

输出数据 3

72

Note

For the first example, the following 99 arrays have an ascent: [1,2],[1,2],[1,3],[1,3],[1,4],[1,4],[2,3],[2,4],[3,4][1, 2], [1, 2], [1, 3], [1, 3], [1, 4], [1, 4], [2, 3], [2, 4], [3, 4]. Arrays with the same contents are counted as their occurences.