An array A consisting of N integers is given. A triplet of indices $($P$,$Q$,$R$)$ is called a triangle if $0<=$P A$[$R$]$

A$[$Q$]+$ A$[$R$]>$ A$[$P$]$

A$[$R$]+$ A$[$P$]>$ A$[$Q$]$

The perimeter of such traingle equals A$[$P$]+$ A$[$Q$]>$ A$[$R$].$

For example consider the following array A:

A$[0]=10$

A$[1]=2$

A$[2]=5$

A$[3]=1$

A$[4]=8$

A$[5]=20$

Triplet $(0,2,4)$ iss a triangle and its perimeter equals $10+5+8=23.$ There is no other triangle in this array with a larger perimeter.

Note that the inequality must hold between P$,$Q$,$R$,$ but it is accepted that e$.$g$.$ A$[$P$]=$ A$[$Q$\}$ consider the following array A:

A$[0]=8$

A$[1]=4$

A$[2]=8$

A$[3]=9$

A$[4]=7$

Triplet $(0,2,3)$ is a triangle and its perimeter equals $8+8+9=25.$

Write a fucntion:

func Solution$($A $[]$int$)$ int

that, given an array A on N integers returns the maximum perimeter of any triangle in this array. The function should return $-1$ if there are no triangles. for example

A$[0]=10$

A$[1]=2$

A$[2]=5$

A$[3]=1$

A$[4]=8$

A$[5]=20$

the function should return $23$ as explained above. Given array A such that:

A$[0]=5$

A$[1]=10$

A$[2]=18$

A$[3]=7$

A$[4]=8$

A$[5]=3$

The function should return $25$: the triangle with maximum perimeter is $(1,3,4).$

While for an array A:

A$[0]=10$

A$[1]=20$

A$[2]=30$

The function should return $-1$ as it is impossible to create a triangle.

and for an array A:

A$[0]=8$

A$[1]=4$

A$[2]=8$

A$[3]=9$

A$[4]=7$

the function should return $25$ as explained above.

Write an efficient algorithm for followiing assumption:

N is an integer within the range $[0,....,100000]$;

each element of array A is an integer within the range $[1,..\mathrm{.}100,000,000]$