У древном подруму Комисије за жалбе, налази се \(N\) гомила такмичарских жалби поређаних у низ - на \(i\)-тој гомили се налази \(a_i\) жалби. Дошло је време да се и те жалбе одбију па је Главни Архиватор Ђорђе Кавурмов добио задатак да подели гомиле члановима комисије. Кавурмов планира да подели ове гомиле жалби у хрпе (веће гомиле) - узастопне поднизове гомила жалби при чему ће свака гомила жалби припадати тачно једној хрпи (поднизу).

Међутим, то није тривијалан посао јер величине хрпи морају бити таман (акценат на друго ‘а’) тј. ни превелике ни премале. Прецизније, за сваку хрпу мора важити да њена величина (број гомила жалби у њој, тј. дужина подниза) није мања од најмање гомиле која јој припада (јер то нема смисла) и да није већа од највеће гомиле која јој припада (јер је то безвезе). Како Архиватор не воли да ради, он је одлучио да седи и размишља на колико начина може поделити дати низ гомила на хрпе. Заправо, одлучио је само да седи а размишљање препушта вама - као награду, проследиће вашу жалбу некоме ко их заправо чита пре одбијања.

Описи функција

Потребно је да имплементирате функцију

• \(TamanPodela(N, a[\ldots])\)

где је \(N\) - број гомила жалби док је \(a\) низ који описује гомиле жалби: \(i\)-та гомила садржи \(a_i\) жалби. Низ \(a\) је индексиран од 1. Ова функција мора да врати један цео број – тражени број подела по модулу \(1.000.000.007\) \((10^9 + 7)\). Обратити пажњу да решење мора бити у сегменту \([0, 10^9 + 6]\).

Пример

Нека је \(N = 7\) и \(a = [1, 6, 2, 3, 4, 3, 4]\). Тада је низ од ових 7 гомила жалби могуће поделити на хрпе на следећих \(6\) начина: | 1 | 6 2 3 4 3 4 |, | 1 6 2 | 3 4 3 4 |, | 1 6 2 3 | 4 3 4 |, | 1 | 6 2 | 3 4 3 4 |, | 1 | 6 2 3 | 4 3 4 |, | 1 6 | 2 3 | 4 3 4 |; дакле, у овом случају ваша функција мора вратити број \(6\) \(mod\) \((10^9 + 7)\) \(=\) \(6\). Обрадити пажњу да нпр. подела | 1 6 | 2 3 4 3 4 | није валидна јер је величина (дужина) десне хрпе \(5\) што је веће од највеће гомиле која јој припада (\(4\)); такође, подела | 1 6 2 | 3 4 | 3 4 | није валидна јер је величина последње две хрпе \(2\) што је мање од најмањих гомила које им припадају (у оба случаја \(3\)).

Ограничења

• \(1 \leq N \leq 500.000\)
• За свако \(i = \overline{1,N}\) важи \(1 \leq a_i \leq N\)

Подзадаци

• Подзадатак 1 [9 поена]: \(N \leq 1.000\).
• Подзадатак 2 [10 поена]: \(N \leq 100.000\), \(a_i \leq 500\).
• Подзадатак 3 [12 поена]: У низу \(a\) постоје тачно 2 различите вредности.
• Подзадатак 4 [24 поена]: За сваки паран индекс \(i\) важи \(a_i = N\).
• Подзадатак 5 [45 поена]: Нема додатних ограничења.

Детаљи имплементације

Потребно је да пошаљете тачно један фајл taman.cpp или taman.pas, који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

У зависности од програмског језика који користите, ваша функција/процедура мора бити следећег облика:

Вашим програмима је дозвољено да мењају садржај низова/матрица, али не смеју да приступају ван граница датих низова.

Тестирање и експериментисање

Уз задатак, обезбеђени су вам “template” фајлови code.cpp и code.pas које можете користити и мењати по потреби. Такође су вам обезбеђени програми grader.cpp, grader.pas који служе да лакше тестирате кодове. Ови програми учитавају са стандардног улаза следеће податке:

• У првом реду број \(N\),
• У наредном реду \(N\) бројева, елементе низа \(a\)

а затим позивају вашу функцију са учитаним параметрима и, на крају, вредност коју ваша функција враћа исписују на стандардни излаз. Кодове ових програма можете мењати по потреби.