Introduction
Problem statement
We are given an array of length n. Our task is to find the sum of beauty in the array of every index ( 1<= index < n1 )
Beauty of each ith element equals, where 1 <= i < n1,
 2, if all the elements on the left of the ith element are smaller and all the elements on its right are greater than the ith element, a[j] < a[i] < a[k] for all 0 <= j < i < k < n
 1, if the element just before the ith element is smaller and the element just after the ith element is greater than the ith element, a[i1] < a[i] < a[i+1] and the previous condition is not satisfied.
 0, if none of the previous conditions is satisfied.
Sample Examples
Example 1:
Input: a[] = { 5, 7, 8, 1, 4, 9 }
Output: 2
Explanation
The beauty of a[1] = 1
The beauty of a[2] = 0
The beauty of a[3] = 0
The beauty of a[4] = 1
Sum of beauty in the array = 1 + 0 + 0 + 1 = 2
Example 2:
Input: a[] = { 6, 3, 4, 8, 2 }
Output: 1
Explanation
The beauty of a[1] = 0
The beauty of a[2] = 1
The beauty of a[3] = 0
Sum of beauty in the array = 0 + 1 + 0 = 1
Also see, Euclid GCD Algorithm
Bruteforce approach
For the ith element to have a beauty value of 2, it must be larger than all the elements on its left and smaller than all the elements on its right. As a result, it should be greater than the maximum of all left elements and smaller than the minimum of all the right elements.
For the beauty value of the ith element to be 1, it should firstly not satisfy the above condition, and secondly, the ith element should be greater than the (i  1)th element and lesser than (i + 1)th element
Step of algorithm
 For each ith element ( 1 <= i < n1 ), traverse to its left and right.
 Create a variable ans = 0 to store the sum of beauty in the Array.
 If all elements on the left side are smaller and all elements on the right side are greater than the current element, add 2 to the ans.
 If the above condition is false and the element just before the current element is smaller, and the element just after the current element is greater than the current element, add 1 to ans.

After checking for all the elements, return the value of ans.
Let's understand the above approach with an example:

For a[1] = 3, it doesnâ€™t satisfy any of the above condition, beauty = 0

For a[2] = 4, a[1] < a[2] < a[3], beauty = 1
 For a[3] = 8, it doesn't satisfy any of the above conditions, beauty = 0
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
int sum_of_beauty(int a[], int n)
{
int ans = 0; // stores the sum of beauty in the array
for (int i = 1; i < n  1; i++)
{
bool flag = true;
for (int j = 0; j < i; j++) // checking left side
{
if ( a[j] >= a[i])
flag = false;
}
for (int k = i + 1; k < n; k++) // checking right side
{
if (a[k] <= a[i])
flag = false;
}
if (flag == true)
ans += 2;
else if (a[i  1] < a[i] && a[i + 1] > a[i])
ans += 1;
}
return ans;
}
int main()
{
int a[] = { 5, 7, 8, 1, 4, 9 };
int n = sizeof(a) / sizeof(a[0]);
cout << sum_of_beauty(a, n) << endl;
}
Output:
2
Complexity Analysis
Time complexity: O(n^2), as we are using two nested loops, one for traversing the array and the other for checking its left and the right side, where n is the size of the given array.
Space complexity: O(1), as we are using constant extra space.