Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. New Year and Ascent Sequence

time limit per test

2 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputA sequence $$$a = [a_1, a_2, \ldots, a_l]$$$ of length $$$l$$$ has an ascent if there exists a pair of indices $$$(i, j)$$$ such that $$$1 \le i < j \le l$$$ and $$$a_i < a_j$$$. For example, the sequence $$$[0, 2, 0, 2, 0]$$$ has an ascent because of the pair $$$(1, 4)$$$, but the sequence $$$[4, 3, 3, 3, 1]$$$ doesn't have an ascent.

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

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

Gyeonggeun will consider all $$$n^2$$$ pairs of sequences $$$s_x$$$ and $$$s_y$$$ ($$$1 \le x, y \le n$$$), and will check if its concatenation $$$s_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, y$$$) of sequences $$$s_1, s_2, \ldots, s_n$$$ whose concatenation $$$s_x + s_y$$$ contains an ascent.

Input

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

The next $$$n$$$ lines contain the number $$$l_i$$$ ($$$1 \le l_i$$$) denoting the length of $$$s_i$$$, followed by $$$l_i$$$ integers $$$s_{i, 1}, s_{i, 2}, \ldots, s_{i, l_i}$$$ ($$$0 \le s_{i, j} \le 10^6$$$) denoting the sequence $$$s_i$$$.

It is guaranteed that the sum of all $$$l_i$$$ does not exceed $$$100\,000$$$.

Output

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

Examples

Input

5 1 1 1 1 1 2 1 4 1 3

Output

9

Input

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

Output

7

Input

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

Output

72

Note

For the first example, the following $$$9$$$ arrays have an ascent: $$$[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.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/08/2020 18:39:04 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|