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
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 5e2 + 5;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int sum[nmax];
int _freq[40000000 + 5];
#define freq (_freq + 20000000)

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n;
   cin >> n;

   for(int i = 1; i <= n; i++) cin >> sum[i], sum[i] += sum[i - 1];

   ll total = 0;

   for(int r23 = 1; r23 <= n; r23 ++) {
      for(int l2 = 1; l2 <= r23; l2++) {
         for(int l3 = l2 + 1; l3 <= r23; l3++)
            total += freq[-(sum[r23] - sum[l2 - 1] + sum[r23] - sum[l3 - 1])];
         freq[sum[r23] - sum[l2 - 1]]++;
      }
   }
   
   fill(_freq, _freq + 40000000 + 3, 0);
   
   for(int r12 = n; r12 > 0; r12--) {
      for(int l1 = 1; l1 < r12; l1++) {
         for(int l2 = l1 + 1; l2 <= r12; l2++)
            total += freq[-(sum[r12] - sum[l1 - 1] + sum[r12] - sum[l2 - 1])];
      }
      for(int l3 = 1; l3 <= r12; l3++)
         freq[sum[r12] - sum[l3 - 1]]++;
   }
   //cerr << sizeof(_freq) << '\n';
   fill(_freq, _freq + 40000000 + 3, 0);
   
   //cerr << total << '\n';
   
   
   for(int linker = 1; linker <= n; linker++) {
      {
      int r2 = linker;
      for(int r3 = r2 + 1; r3 <= n; r3++)
         for(int l3 = 1; l3 <= r3; l3++)
            //cerr << "  =  " << r2 << '\t' << l3 << ' ' << r3 << '\n',
            total += freq[-(sum[r3] - sum[l3 - 1] + sum[r2])];
      }
      
      {
      int r1 = linker;
      for(int l1 = 1; l1 <= r1; l1++)
         for(int l2 = 1; l2 <= r1 + 1; l2++)
            freq[sum[r1] - sum[l1 - 1] - sum[l2 - 1]]++;
      }
      
      {
      int l2 = linker + 1;
      for(int r1 = l2 - 2; r1 >= 1; r1--)
         for(int l1 = 1; l1 <= r1; l1++)
            freq[sum[r1] - sum[l1 - 1] - sum[l2 - 1]]++;
      }
   }
   
   cout << total << '\n';
   
}



/**
 *         
 * o o o o o o o o o o o o o o o o
 *       a           b c
 *           i     j       k
 * 
 * i + j + k = a + b + c
 * (i - a)
 * 
 * 
 * 
 *  
  -- Rugaciunile mele
*/