# Problem Link

# Difficulty

Simple

# Pre-requisites

Simple dynamic programming

# Problem

Count the number of non-decreasing subarrays of the given array **A[]**.

# How to get 20 points

Let’s choose the left bound, say **L**. After the left bound is fixed, let’s choose the right bound, say **R**. And now, let’s check that the subarray **A[L, R]** is non-decreasing.

In other words, let’s iterate through all possible subarrays and then, for each of them, check whether it is a non-descreasing one or not.

Choosing the left bound takes **O(N)** operations, choosing the right bound takes **O(N)** operations too, and checking subarray also takes **O(N)** operations. Since these operations are nested, hence the total complexity will be **O(N ^{3})**.

This solution is good enough to solve the first subtask.

# How to get 50 points

Let’s choose the left bound, say **L**. Let the right bound, say **R**, be equal to **L** initially. Then while the elements are non-decreasing keep increasing the right bound **R**. At some moment, you will certainly stop. The amount of non-decreasing subarrays with the left bound at **L** will be equal to **R-L+1** for every fixed **L**. The sum of all this values is the answer to the problem.

Choosing the left bound takes **O(N)** operations, and finding the right bound takes **O(N)** operations. Since these operations are nested, the complexity of the whole solution will be **O(N ^{2})**.

This solution solves the first and the second subtask, but is still not good enough to get the full points.

# How to get 100 points

Let’s introduce an array **B[]** of **N** elements, where the **i**^{th} element of **B[]** defines the amount of the correct subarrays with the *right* bound equal to **i**.

Now, let’s give the rules for calculating the **i**^{th} element of **B[]**:

- if
**A[i-1] ≤ A***, then* since every non-decreasing subarray that ends at the*B*= B[i-1] + 1**(i-1)**^{th}element can be continued with the**i**^{th}element without loss of non-decreasingness and one more non-decreasing subarray that ends at the**i**^{th}element is**A[i, i]**. - if
**A[i-1] > A***, then* since any subarray that ends at the*B*= 1**(i-1)**^{th}element will lose its’ non-decreasingness if continued with the**i**^{th}element, so the only suitable subarray will be**A[i, i]**.

So, the answer will be equal to the sum of all elements of **B[]**. The complexity is **O(N)**, because the computation of the array **B** turns out to be a single for-loop with a condition for the computation of **B*** inside.

# Setter’s Solution

Can be found here

# Tester’s Solution

Can be found here