AlgoLiga 2018

Masz daną permutację liczb od 1 do n. Twoim zadaniem jest stwierdzenie ile najmniej krawędzi musi mieć skierowany graf acykliczny, aby wierzchołki (ponumerowane od 1 do n) zapisane w minimalnym leksykograficznie porządku topologicznym były takie same jak dana permutacja oraz ile takich różnych grafów istnieje? Grafy są uważane za różne, jeśli w jednym istnieje krawędź, która nie istnieje w drugim. Graf może być niespójny.

Wejście

W pierwszej linii wejścia znajduje się liczba testów t ∈ [1;1000].

Każdy test składa się z dwóch linii wejścia. W pierwszej linii znajduje się liczba natuarlna n ∈ [1;10⁶]. W drugiej linii znajduje się n liczb naturalnych przedstawiających daną permutację. Suma n we wszystkich testach nie przekracza 10⁶.

Wyjście

Dla każdego testu należy wypisać najmniejszą liczbę krawędzi oraz ilość różnych grafów zawierających minimalną liczbę krawędzi modulo 10⁹+7.

Przykład

Wejście:

2
3
1 2 3
3
3 2 1

Wyjście:

0 1
2 1