I have some problems with code for my classes. Even though it works correctly, I run out of time for half of the examples. Here’s the task (I really did my best trying to translate it):

You have a permutation of numbers 1,2,…,n for some n. All consecutive numbers of permutations together create sequence aā, aā, aā. Your task is to count how many arithmetic substrings of length 3 are present.

Input: In first line there is a number n (1 <= n <= 200 000). In the second line there is n numbers aā, aā, aā representing our permutation.

Output: The program needs to print out amount of arithmetic substrings of length 3 for permutations from entry. You can assume that the result won’t be bigger than 1 000 000.

NOTE: arithmetic substrings most likely stand for arithmetic progression or something like that

```
#include <iostream>
using namespace std;
int main()
{
int input_length;
cin >> input_length;
int correct_sequences = 0;
bool* whether_itroduced = new bool(input_length + 1){0}; // true - if number was already introduced and false otherwise.
for (int i = 0; i < input_length; i++)
{
int a;
cin >> a;
whether_itroduced(a) = true;
int range = min(input_length - a, a - 1); // max or min number that may be in the subsequence e.g. if introduced number a = 3, and all numbers are six, max range is 2 (3 - 2 = 1 and 3 + 2 = 5, so the longest possible subsequence is 1, 3, 5)
for (int r = range * -1; r <= range; r++) // r - there is a formula used to count arithmetic sequences -> an-1 = a1-r, an = a1, an+1 = a1+r, I have no idea how to explain it
{
if (r == 0) continue; // r cannot be 0
if (whether_itroduced(a - r) && !whether_itroduced(a + r))
correct_sequences++;
}
}
cout << correct_sequences;
}
```

example input: `5 1 5 4 2 3`

correct output: `2`

// {1,2,3} and {5,4,3}

example input: `5 1 2 3 4 5`

correct output: `4`

// {1,2,3} {2,3,4} {3,4,5} {1,3,5}

example input: `10 1 5 9 7 4 3 6 10 2 8`

correct output: `4`

// {4,3,2} {1,5,9} {5,4,3} {4,6,8}

I need to somehow come up with another algorithm that is less than quadratic in time. I can’t really see all of the inputs and correct outputs, but I know that the biggest ‘n’ number is about 32000, so it’s most likely that I run out of time because of the algorithm. Do you have any ideas about how can I improve it and make it work faster? Thanks for help!