Questions

HandsOn $>$ Govered ranges

A range is set of consecutive numbers e$.$g$.$ range $1,4$ is same as set $\{1,2,3,4\}.$

A sub$-$array is said to be covering a group of ranges if:

Each element of this sub$-$array belongs to at least one of the covered ranges.

All values belonging to each of the covered range must be present at least once in the sub$-$array.

You will be given an array $a$ of length $n$ with $q$ queries.

Answer to each query $l,r$ is the minimum number of ranges covering the sub$-$array a$[$l$..$r$].$

Find the sum of answers to all qqueries. Since the answer may be large return it modulo ${10}^9+7.$

Input Format

The first line contains an integer, $n,$ denoting the size of array $a.$ Each line $i$ of the $n$ subsequent lines $($where $0i$