human
A sequence a = [a_1, a_2, …, a_l] of length l has an ascent if there exists a pair of indices (i, j) such that 1 ≤ i < j ≤ 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, …, s_n which may have different lengths. 

Gyeonggeun will consider all n^2 pairs of sequences s_x and s_y (1 ≤ x, y ≤ 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, …, s_n whose concatenation s_x + s_y contains an ascent.

Input

The first line contains the number n (1 ≤ n ≤ 100 000) denoting the number of sequences.

The next n lines contain the number l_i (1 ≤ l_i) denoting the length of s_i, followed by l_i integers s_{i, 1}, s_{i, 2}, …, s_{i, l_i} (0 ≤ s_{i, j} ≤ 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.
impor
assistant
#Here is Python code to print a single integer, the number of pairs of sequences whose concatenation has an ascent.
t bisect
class Solution(object):

    def check(self,seq):
        t_min=seq[0]
        for i in range(1,len(seq)):
            if seq[i]>t_min:
                return True
            elif seq[i]<t_min:
                t_min=seq[i]
        return False
    
    def solve(self,seqs):
        min_stack=[]
        q_seq=[]
        p_seq=[]
        for s in seqs:
            if self.check(s):
                p_seq.append(s)
            else:
                q_seq.append(s)
                min_stack.append(min(s))
                
        min_stack=sorted(min_stack)
        q_ans=0
        for s in q_seq:
            
            temp_ans=bisect.bisect_left(min_stack,max(s))
            q_ans+=temp_ans
            
        lp=len(p_seq)
        lq=len(q_seq)
            
        return lp*lp+2*lp*lq+q_ans
        
        

if __name__=="__main__":
	input_len=int(raw_input().strip())
	seqs=[]
	for _ in range(0,input_len):
		temp_seq=map(int,raw_input().split(" "))[1:]
		seqs.append(temp_seq)
	T=Solution()
	print T.solve(seqs)