Costel are de rezolvat o temă grea la matematică: având la dispoziţie N numere naturale nenule trebuie să aşeze între acestea 2 operaţii de înmulţire şi N-3 operaţii de adunare, astfel încât rezultatul calculelor să fie cel mai mare posibil. Nu este permisă modificarea ordinii numerelor date.

De exemplu, dacă N=5 şi numerele sunt 4, 7, 1, 5, 3, operaţiile pot fi aşezate 4+7*1+5*3, 4*7*1+5+3, e.t.c

Cerinţă

Scrieţi un program care să aşeze două operaţii de înmulţire şi N-3 operaţii de adunare între cele N valori date astfel încât valoarea expresiei obţinute să fie maximă.

Date de intrare

Fișierul de intrare expresie8.in are următoarea structură:

• Pe prima linie se află un număr natural N, reprezentând numărul elementelor date.
• Pe următoarele linii se află cele N numere naturale date, fiecare pe câte o linie.

Date de ieșire

Fișierul de ieșire expresie8.out va conține pe prima linie valoarea maximă obţinută prin evaluarea expresiei.

Restricții și precizări

• 4 <= N <= 1000
• Numerele date sunt numere naturale între 1 şi 10000

Exemplu

expresie8.in

5
4
7
1
5
3

expresie8.out

44

Explicație

Valoarea maximă se obţine prin aşezarea operaţiilor sub forma: 4 * 7 + 1 + 5*3.

#include <bits/stdc++.h>
using namespace std;
int a[1002];
int main ()
{
    ifstream fin("expresie8.in");
    ofstream fout("expresie8.out");
    int n;
    unsigned long long s=0,si=0,smax=0,s1=0;
    fin >> n;
    for (int i=1;i<=n;++i)
      {
          fin >> a[i];si+=a[i];
      }  
    for (int i=2;i<=n-2;++i)
        {
            for (int j=i+2;j<=n;++j)
            {
                s=si+1LL*a[i]*a[i-1]-a[i]-a[i-1]+ 1LL*a[j]*a[j-1]-a[j]-a[j-1];
                if(s > smax)
                smax=s;
            }
        }
        for (int i=3;i<=n;++i)
        {
            s=si+ 1LL*a[i-2]*a[i-1]*a[i]-a[i-2]-a[i-1]-a[i];
            if (s >smax)
                smax=s;
        }
        fout <<smax;
        fin.close();
        fout.close();
        return 0;


}