codeforces#P1083D. The Fair Nut's getting crazy
The Fair Nut's getting crazy
Description
The Fair Nut has found an array of integers. We call subarray a sequence of consecutive elements of an array with indexes from to , i.e. .
No one knows the reason, but he calls a pair of subsegments good if and only if the following conditions are satisfied:
- These subsegments should not be nested. That is, each of the subsegments should contain an element (as an index) that does not belong to another subsegment.
- Subsegments intersect and each element that belongs to the intersection belongs each of segments only once.
For example . Pairs and ) — are good, but and — are not (subsegment contains subsegment , integer belongs both segments, but occurs twice in subsegment ).
Help the Fair Nut to find out the number of pairs of good subsegments! The answer can be rather big so print it modulo .
The first line contains a single integer () — the length of array .
The second line contains integers () — the array elements.
Print single integer — the number of pairs of good subsegments modulo .
Input
The first line contains a single integer () — the length of array .
The second line contains integers () — the array elements.
Output
Print single integer — the number of pairs of good subsegments modulo .
Samples
Note
In the first example, there is only one pair of good subsegments: .
In the second example, there are four pairs of good subsegments: