1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <vector>
using namespace std;

#define N 500

typedef tuple<int, int> tii;
typedef tuple<int, int, int> tiii;

int A[N];
int C[N + 1];

int PERMS3[6][3] = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2},
                    {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};

template <typename T> bool all_unique(T a, T b, T c) {
  return a != b && a != c && b != c;
}

bool valid(tiii idxs1, tiii idxs2) {
  int i = get<0>(idxs1), j = get<1>(idxs1), k = get<2>(idxs1);
  int ii = get<0>(idxs2), jj = get<1>(idxs2), kk = get<2>(idxs2);
  return (i < ii && j < jj && k < kk &&
          all_unique(make_pair(i, ii), make_pair(j, jj), make_pair(k, kk)));
}

int count_valid(tiii idxs1, tiii idxs2) {
  tii tmp[3];
  set<tuple<tii, tii, tii>> ok;
  for (size_t i = 0; i < 6; i++) {
    int aidxs1[3] = {get<0>(idxs1), get<1>(idxs1), get<2>(idxs1)};
    tiii permidxs1 = {aidxs1[PERMS3[i][0]], aidxs1[PERMS3[i][1]],
                      aidxs1[PERMS3[i][2]]};
    if (valid(permidxs1, idxs2)) {
      tmp[0] = make_pair(get<0>(permidxs1), get<0>(idxs2));
      tmp[1] = make_pair(get<1>(permidxs1), get<1>(idxs2));
      tmp[2] = make_pair(get<2>(permidxs1), get<2>(idxs2));
      sort(tmp, tmp + 3);
      ok.insert({tmp[0], tmp[1], tmp[2]});
    }
  }
  return ok.size();
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  size_t n;
  uint64_t out = 0;
  int v, s = 0;
  cin >> n;
  C[0] = s = 0;
  for (size_t i = 0; i < n; i++) {
    cin >> v;
    A[i] = v;
    s += v;
    C[i + 1] = s;
  }

  map<int, vector<tiii>> d;
  n += 1;
  for (size_t i = 0; i < n; i++) {
    for (size_t j = i; j < n; j++) {
      for (size_t k = j; k < n; k++) {
        v = C[i] + C[j] + C[k];
        if (!d.contains(v)) {
          d[v] = vector<tiii>();
        }
        d[v].push_back({i, j, k});
      }
    }
  }

  for (auto dit = d.begin(); dit != d.end(); dit++) {
    auto v = dit->second;
    for (auto vit1 = v.begin(); vit1 != v.end(); vit1++) {
      for (auto vit2 = vit1 + 1; vit2 != v.end(); vit2++) {
        out += count_valid(*vit1, *vit2);
      }
    }
  }
  cout << out << endl;

  return 0;
}