B. New Year and Ascent Sequence

链接：https://codeforces.com/contest/1284/problem/B

A sequence a=[a1,a2,…,al]a=[a1,a2,…,al] of length ll has an ascent if there exists a pair of indices (i,j)(i,j) such that 1≤i<j≤l1≤i<j≤l and ai<ajai<aj. 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,…,sns1,s2,…,sn which may have different lengths.

Gyeonggeun will consider all n2n2 pairs of sequences sxsx and sysy (1≤x,y≤n1≤x,y≤n), and will check if its concatenation sx+sysx+sy 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,…,sns1,s2,…,sn whose concatenation sx+sysx+sy contains an ascent.

Input

The first line contains the number nn (1≤n≤1000001≤n≤100000) denoting the number of sequences.

The next nn lines contain the number lili (1≤li1≤li) denoting the length of sisi, followed by lili integers si,1,si,2,…,si,lisi,1,si,2,…,si,li (0≤si,j≤1060≤si,j≤106) denoting the sequence sisi.

It is guaranteed that the sum of all lili does not exceed 100000100000.

Output

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

Examples

input

Copy

5
1 1
1 1
1 2
1 4
1 3

output

Copy

9

input

Copy

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

output

Copy

7

input

Copy

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

Copy

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.

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,t,d,s,k;
long long l[1000001];
long long a[1000001];
long long f[1000001],e[1000001];
long long flag[1000001];
int main()
{
	cin>>n;
	s=0;
	k=0;
	for(int i=1;i<=n;i++)
	{
		cin>>l[i];
		flag[i]=0;
		a[0]=1e9+7;
		for(int j=1;j<=l[i];j++)
		{
			 cin>>a[j];
			 if(a[j]<=a[j-1])
			 continue;
			 else
			 flag[i]=1;
		} 
		if(flag[i]==0)
		{
			k++;
			f[k]=a[1];
			e[k]=a[l[i]];
		}
		else
		{
			k++;
			f[k]=1e9+7;
			e[k]=-1;
		}
	}
	sort(f+1,f+1+k);
	for(int i=1;i<=k;i++)
	{
		d=upper_bound(f+1,f+1+k,e[i])-f;
		s+=k-d+1;
	}
	cout<<s<<endl;
}