Safe Partition

All submissions for this problem are available.
Read problems statements in Hindi, Mandarin chinese , Russian and Vietnamese as well.
It's summer — the time for holidays! Chef finally finished all university exams. Now he can rest and play with sequences. Today, Chef took a sequence $A$ with $N$ elements. He wants to partition this sequence into an arbitrary number of nonempty contiguous subsequences (i.e. each of the subsequences has to consist of one or more consecutive elements of the original sequence). Each element of the original sequence must belong to exactly one subsequence. This would be easy for Chef, so he is only interested in *safe partitions* of $A$. A safe partition is a partition into subsequences $S_1, S_2, \dots, S_K$ such that for each valid $i$, $\mathrm{min}(S_i) \le S_i \le \mathrm{max}(S_i)$ — that is, for each subsequence in this partition, its length is greater or equal to its smallest element and smaller or equal to its largest element. Finding one safe partition would still be easy for Chef, so he wants to find the number of safe partitions of $A$. Since this number could be very big, please compute it modulo $1000000007$ ($10^9 + 7$). ### Input  The first line of the input contains a single integer $N$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \dots, A_N$. ### Output Print a single line containing one integer — the number of safe partitions of $A$ modulo $10^9+7$. ### Constraints  $1 \le N \le 5 \cdot 10^5$  $1 \le A_i \le N$ for each valid $i$ ### Subtasks **Subtask #1 (10 points):** $1 \le N \le 1,000$ **Subtask #2 (10 points):**  $1 \le N \le 10^5$  $1 \le A_i \le 500$ for each valid $i$ **Subtask #3 (15 points):** there are exactly two different values of elements of $A$ **Subtask #4 (25 points):** $A_{2i}=N$ for each valid $i$ **Subtask #5 (40 points):** original constraints ### Example Input ``` 7 1 6 2 3 4 3 4 ``` ### Example Output ``` 6 ``` ### Explanation The six safe partitions are:  $[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]$Author:  allllekssssa 
Editorial  https://discuss.codechef.com/problems/SAFPAR 
Tags  allllekssssa, allllekssssa, aug18, hard, likecs, long_challenge 
Date Added:  22072018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 