{"raw_statement":[{"iden":"statement","content":"Аттракцион «Американские горки» представляет собой рельсовый трек, размещенный на опорах. Известна высота каждой опоры. Для рекламы аттракциона необходимо выделить один из его фрагментов (несколько подряд идущих опор с рельсовым треком) световой подсветкой. При этом необходимо выделить такой фрагмент трека, на котором была бы «горка», т.е. на выделенном участке трека была бы точка, которая находилась бы строго выше начала и строго выше конца выделенного фрагмента трека.\n\nВладелец аттракциона для экономии хочет найти подходящий участок минимальной длины, удовлетворяющий условию наличию «горки» на этом участке.\n\nПервая строка входных данных содержит число $N$ — количество опор аттракциона. Следующие $N$ строк содержат информацию о высотах опор при движении от начала к концу аттракциона. Все числа натуральные и не превосходящие $10^5$.\n\nПрограмма должна вывести два числа — номер первой и последней подходящей опоры. Опоры нумеруются числами от $1$ до $N$. Если фрагмента, удовлетворяющего условиям, не существует, программа должна вывести одно число 0. Если подходящих ответов несколько, нужно вывести любой из них.\n\nРешение, правильно работающее только для случав, когда все исходные числа не превосходят 100, будет оцениваться в 40 баллов. В 100 баллов будет оцениваться решение, правильно работающее, когда все числа не превосходят $10^5$.\n\nПояснение к первому примеру. Дано 7 опор с высотами 18, 10, 15, 20, 20, 20, 1, 3. Самый короткий участок, содержащий «горку» — это 15, 20, 20, 10. Он начинается опорой номер 3 и заканчивается опорой номер 6.\n\nПояснение ко второму примеру. Высоты опор убывают, поэтому участка с «горкой» нет.\n\n"},{"iden":"входные данные","content":"Первая строка входных данных содержит число $N$ — количество опор аттракциона. Следующие $N$ строк содержат информацию о высотах опор при движении от начала к концу аттракциона. Все числа натуральные и не превосходящие $10^5$."},{"iden":"выходные данные","content":"Программа должна вывести два числа — номер первой и последней подходящей опоры. Опоры нумеруются числами от $1$ до $N$. Если фрагмента, удовлетворяющего условиям, не существует, программа должна вывести одно число 0. Если подходящих ответов несколько, нужно вывести любой из них."},{"iden":"система оценки","content":"Решение, правильно работающее только для случав, когда все исходные числа не превосходят 100, будет оцениваться в 40 баллов. В 100 баллов будет оцениваться решение, правильно работающее, когда все числа не превосходят $10^5$."},{"iden":"примеры","content":"Входные данные7\n18\n10\n15\n20\n20\n10\n3\nВыходные данные3\n6\nВходные данные3\n9\n8\n5\nВыходные данные0\n"},{"iden":"примечание","content":"Пояснение к первому примеру. Дано 7 опор с высотами 18, 10, 15, 20, 20, 20, 1, 3. Самый короткий участок, содержащий «горку» — это 15, 20, 20, 10. Он начинается опорой номер 3 и заканчивается опорой номер 6.Пояснение ко второму примеру. Высоты опор убывают, поэтому участка с «горкой» нет."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, p, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq p \\leq n \\leq 2500 $ and $ 1 \\leq m \\leq 2500 $.  \nLet $ C = (c_1, c_2, \\dots, c_n) $ be a sequence of length $ n $, where each $ c_i \\in \\{1, 2, \\dots, m\\} $.\n\n**Constraints**  \nFor every contiguous subsequence (sub-combo) of length $ p $, i.e., for every $ i \\in \\{1, 2, \\dots, n - p + 1\\} $, the subsequence $ (c_i, c_{i+1}, \\dots, c_{i+p-1}) $ must be a palindrome.\n\n**Objective**  \nCount the number of such sequences $ C $ modulo $ 10^9 + 7 $.","simple_statement":"Given n, p, m: count the number of sequences of length n using m moves such that every contiguous subsequence of length p is a palindrome. Return answer mod 10^9+7.","has_page_source":false}