Bobo is tired of all kinds of hard LIS problems,so he decides to make himself some easier one.He defines f be the length of longest increasing subsequence of sequence. Bobo would like to know g which is the number of pairs where f = k.
Bobo is tired of all kinds of hard LIS (Longest Increasing Subsequence) problems,
so he decides to make himself some easier one.
Bobo has n pairs
(a_1, b_1), (a_2, b_2), dots, (a_n, b_n)
(a
1
,b
1
),(a
2
,b
2
),…,(a
n
,b
n
)
where
1 leq a_i, b_i leq m
1≤a
i
,b
i
≤m holds for all i.
He defines f(i, j) be the length of longest increasing subsequence of sequence
{a_i, b_i, a_j, b_j}
{a
i
,b
i
,a
j
,b
j
}.
It's clear that
1 leq f(i, j) leq 4
1≤f(i,j)≤4.
Bobo would like to know g(k) which is the number of pairs (i, j) where f(i, j) = k.
Note that a sequence labeled with
{i_1, i_2, dots, i_k}
{i
1
,i
2
,…,i
k
} is an increasing subsequence of
{a_1, a_2, dots, a_n}
{a
1
,a
2
,…,a
n
} only if:
*
1 leq i_1 < i_2 < dots < i_k leq n
1≤i
1
