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.
Using python3 can you solve the prior task?
assistant
#Here is Python code to print a single integer, the number of pairs of sequences whose concatenation has an ascent.

from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
 
# M = mod = 998244353
def factors(n):return sorted(list(set(reduce(list.__add__,([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))))
# def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split(' ')]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n').split(' ')]
def li3():return [int(i) for i in input().rstrip('\n')]

n = val()
l = []
for i in range(n):l.append(li()[1:])
d = {}
minmax = []
for ind,i in enumerate(l):
    currmin,currmax = i[0],i[0]
    d[ind] = 0
    for j in i:
        if j>currmin:
            d[ind] = 1
        currmin = min(currmin,j)
        currmax = max(currmax,j)
    if not d[ind]:
        minmax.append([currmin,currmax])
maxlen,minlen = sorted([i[1] for i in minmax]),sorted([i[0] for i in minmax])
tot = 0
# print(minlen,maxlen,minmax)
# print(l)
# # for i in range(len(l)):
    
for i in range(len(minmax)):
    tot += len(minmax) - br(maxlen,minmax[i][0])

    # print('check : ',i,tot)
# print(tot)
# print(d)
curr = 0
for i in range(len(l)):
    if d[i]:
        tot += (len(l) - (curr)) * 2 - 1
        curr += 1
print(tot)
# for i in l:
#     for j in l:
#         temp = i +j
#         do = 0
#         for k in range(len(temp)):
#             for j in range(k + 1, len(temp)):
#                 if temp[k] < temp[j]:
#                     do = 1
                    
#                     print('- >',*temp,end = " ")
#                     print('- >',end = ' ')
#                     print(temp[k],temp[j])
#                     # print(temp[k],)
#                     break
#             if do:break