Задача №111296. Королевская династия
Глеб очень любит историю. Он приходит в полный восторг, когда ему предлагают изучить историю какой-либо конкретной династии. Глеб очень строго относится к чистоте крови, поэтому при анализе династии он включает в рассмотрение только мужчин, которые являются кровными потомками основателя династии по отцовской линии.
Один из главных методов исторического анализа династии — изучение количества сыновей некоторого ее представителя. Глеб же намеревается произвести настоящую революцию в исследованиях — он намерен изучать не просто количество сыновей, а количество внуков, правнуков, праправнуков и так далее. Однако, династии могли тянуться несколько десятков поколений, а значит общее число кровных потомков очень велико, так что Глебу стало очень тяжело работать. Поскольку на дворе сейчас XXI век, Глеб решил обратиться за помощью к квалифицированным программистам.
Династия представляет собой множество людей, один из которых называется основателем династии, а любой другой представитель династии \(U\) имеет отца \(V\), являющегося представителем династии. При этом \(U\) является сыном \(V\), или потомком \(U\) через \(1\) поколение. Потомком \(U\) через \(k+1\) поколение называется сын \(V\) некоторого потомка \(U\) через \(k\) поколений.
Глеба интересует информация о том, сколько у некоторого представителя династии \(V\) существует потомков через \(k\) поколений. Разумеется, Глеба интересует далеко не один такой вопрос.
В первой строке входного файла содержится одно число \(n\) — количество человек в династии, которую исследует Глеб (\(1 \le n \le 10^5\)), представители династии пронумерованы различными натуральными числами от 1 до \(n\). Далее следуют \(n\) чисел, \(i\)-е из которых задает номер отца \(i\)-го представителя династии, или равно \(-1\), если соответствующий представитель является основателем династии.
Гарантируется, что основатель династии ровно один, и что любой упомянутый представитель династии явялется потомком основателя династии.
В следующей строке содержится число \(m\) — количество вопросов, которое интересует Глеба (\(1 \le m \le 10^5\)). Далее следует \(m\) строк, каждая из которых содержит два целых числа \(v\) и \(k\) (\(1 \le v \le n\), \(1 \le k \le 10^9\)) — номер исследоваемого представителя династии и интересущее Глеба число поколений.
Для каждого вопроса выведите одно число — количество потомков через соответсвующее число поколений у заданного представителя династии.
5 -1 1 2 1 4 2 1 2 4 7
2 0