Задача №113244. Декартовы деревья
Недавно на лекции в университете Вася узнал, что такое декартово дерево. Декартово дерево — это двоичное дерево, в каждом узле которого хранятся два значения: ключ и приоритет. Оно является деревом поиска по множеству ключей и кучей на максимум по приоритетам, то есть
ключ любой вершины в левом поддереве вершины \(v\) меньше, чем ключ вершины \(v\);
ключ любой вершины в правом поддереве вершины \(v\) больше, чем ключ вершины \(v\);
приоритеты сыновей вершины \(v\) не больше, чем приоритет самой вершины \(v\).
На контрольной работе Васе досталась следующая задача: дано \(n\) пар чисел вида (ключ, значение), \(i\)-я из которых выглядит как (\(i\), \(y_i\)), и нужно узнать, сколько существует способов построить декартово дерево, используя как ключ вершины \(i\) число \(i\), а как приоритет — \(y_i\). Поскольку это число может оказаться достаточно большим, требуется найти остаток от его деления на число \(10^9+7\). Два декартовых дерева считаются различными, если у них разные корни, или существует вершина, имеющая разных предков в этих деревьях.Первая строка содержит одно натуральное число \(t\) — число тестовых примеров во входных данных. Далее следуют описания тестов. Описание каждого теста состоит из двух строк. Первая строка содержит одно целое число \(n\) \((1 \le n \le 200 000)\) — количество вершин в дереве. Вторая строка содержит \(n\) целых чисел \(y_i\) \((1 \le yi \le 10^9)\) — приоритет \(i\)-й вершины дерева. Сумма \(n\) по всем тестам не превосходит \(200 000\).
Для каждого теста в отдельной строке выведите одно целое число — количество различных декартовых деревьев, которые можно построить на данном наборе приоритетов, по модулю \(10^9+7\).
Решения, проходящие тесты, в которых в каждом тесте во входных данных выполняется ограничение \(n \le 1500\), набирают не менее 40 баллов.