호석이는 정원이 있는 고급 저택을 샀습니다. 식목일을 맞아서 정원에 나무 한 그루를 심었는데, 이 나무는 N개의 정점으로 이루어져 있습니다. 나무의 정점들은 1번부터 N번 정점으로 이뤄져 있으며, 1번 정점이 뿌리에 가까운 정점입니다. 나무에는 N−1개의 가지가 있는데, 각 가지에는 수가 한 개씩 쓰여 있습니다. 또한, 가지가 A번 정점과 B번 정점을 이어준다면, 둘 중 작은 번호가 1번 정점에 더 가까이 있음이 보장됩니다. 주어진 가지들로 항상 모든 정점이 연결됨을 가정해도 좋습니다.

호석이는 여기서 "나무 막대" 하나를 선택하려고 합니다. 나무 막대란, 연속된 가지들이 한 정점에서 시작하여 더 작은 번호 쪽으로 이동하는 형태를 띄는 것을 의미합니다. 예를 들어, 아래 그림과 같은 나무를 심었다면, 빨간색 모양처럼 8→7→6→5 정점들을 지나는 가지들이나 4→2→1 가지들을 선택하는 것이 올바른 "나무 막대" 중 하나입니다. 이때 나무 막대는 정의상 꼭 2개 이상의 정점으로 이루어져 있어야 함에 유의합니다.

"최고의 나무 막대" 란, 나무 막대 포함된 가지들에 써 있는 수들의 종류가 L가지 이상, R가지 이하인 경우를 의미합니다. 예를 들어 위의 그림에서 8→7→6→5 번 정점을 이용하여 나무 막대를 만든다면, 가지에는 8, 3, 8이라는 수가 써 있으므로 총 2가지의 수가 포함되어 있습니다. 4→2→1번 정점을 이용하였다면, 수는 5만 등장했기에 총 1가지 수가 포함되어 있습니다.

호석이는 심은 나무에서 최고의 나무 막대가 몇 가지나 있을지를 찾고 싶습니다. 나무의 정보와 L, R이 주어졌을 때, 나무에서 최고의 나무 막대가 몇 가지나 존재하는지를 찾아주는 프로그램을 작성해주세요.

본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.