Maximum Group Partitioning for Satisfied Students

In a physical education class, there are $n$ kids lined up and numbered from $1$ to $n$. The teacher wants to partition them into several contiguous groups, such that each group consists of kids with consecutive numbers, and each kid belongs to exactly one group.

Each kid $i$ has a requirement: the size of the group they are in must be at least $c_i$ and at most $d_i$. In other words, if a group covers the kids from index $l$ to $r$, its size is $s = r - l + 1$, and it is valid if and only if for every $i$ with $l \le i \le r$, the inequality $$c_i \le s \le d_i$$ holds.

Your task is to determine, under the condition that all kids are satisfied, the maximum number of groups that can be formed, and the number of ways to partition the kids to achieve this maximum number.

Input Format

The first line contains a single integer $n$. The following $n$ lines each contain two integers $c_i$ and $d_i$.

Output Format

Print two space-separated integers: the maximum number of groups and the number of valid partitioning schemes that achieve this maximum.

inputFormat

The first line contains an integer $n$ (the number of kids). Each of the next $n$ lines contains two integers $c_i$ and $d_i$, where $c_i$ is the minimum group size kid $i$ is satisfied with, and $d_i$ is the maximum group size kid $i$ is satisfied with.

outputFormat

Output two space-separated integers: the maximum number of valid groups that can be formed and the number of ways to form such partitions.

sample

3
1 2
1 1
1 3

3 1