Given array A of N <  = 500000 elements and each A[i] <  = N. Find number of partitions of array into some number of subsegments such that every subsegment has length greater or equal to minimum value of subsegment and smaller or equal to maximum value of subsegment.

Example:
A = {1, 6, 2, 3, 4, 3, 4}
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|

How to solve this problem?