FastPrep

Description

Solutions

Newton's Beautiful Sequence

📚RELATED PROBLEMS

Newton, a curious young mathematician, enjoys exploring the beauty of numerical sequences. Every evening, he sits under his favorite apple tree, contemplating the mathematical elegance hidden within sequences of numbers. To quantify the beauty of a sequence, Newton has created a unique method here’s how he does it:

The initial beauty of the sequence is set to 0.

For every possible contiguous segment of the sequence, he sorts the segment.

He then iterates over the elements of each sorted segment, comparing the current element with the next one, if it exists.

If the next element is greater than the current element by more than 1, he adds 1 to the beauty.

If the contiguous segment contains only 1 element, then it also increases the beauty by 1.

But computing it manually is time-consuming. Therefore, he asks you to write a program to help him in return for those delicious apples.

If the beauty value becomes very large, take the modulo with 10⁹ + 7.

You need to write bruteforce solution only. There are bonus points for bruteforce solution (Don't panic some test cases will not pass for the brute force solution but you will be awarded points)

Input Format

First line of input is the integer n denoting the size of the sequence.

The next line contains n space separated integers denoting the elements of the sequence.

Output Format

Return an integer representing the beauty of the sequence modulo 10⁹ + 7

Another question is same as this question, but it asks for the optimal approach and also the constraints are changed.

Constraints for the other question that asks for optimal approach -

1 ≤ N ≤ 10^5

1 ≤ sequence[i] ≤ N

Example 1:

Input:  sequence = [2, 2, 2, 1, 5]
Output: 9 
Explanation:
      
      The contiguous segments-> [2,2,2,1,5], [2,2,1,5], [2,1,5], [1,5], [5], [2,2], [2,1], [1,5], [5], [2], [2], [1], [5] will become [1,2,2,2,5], [1,2,2,5], [1,2,5], [1,5], [5], [2], [2], [1], [5] respectively.
      
      
      The first 4 adds 1 each to the beauty because the difference between 2 and 5 is greater than 1. Rest any pair does not adds to the beauty from these 4 segments.
      
      
      The last 5 mentioned segments also adds 1 each to the beauty since they contain only 1 element.
      
      
      Rest any contiguous segment has 0 contribution to the beauty of the array.

Constraints:

1 ≤ N ≤ 10³
1 ≤ sequence[i] ≤ N