Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_21_08 - Sortowanie topologiczne i permutacja

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;106]. W drugiej linii znajduje się n liczb naturalnych przedstawiających daną permutację. Suma n we wszystkich testach nie przekracza 106.

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 109+7.

Przykład

Wejście:

2
3
1 2 3
3
3 2 1

Wyjście:

0 1
2 1

Dodane przez:Bartek
Data dodania:2015-03-06
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
Pochodzenie:ALGOLIGA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.