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
112
113
114
115
116
117
#ifdef USE_PALI
#include <pali.hpp>
#else
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
typedef unsigned int uint;
typedef long long lol;
#endif
using namespace std;

void fft(vector<complex<double>>& a)
{
  uint n = static_cast<uint>(a.size());

  static vector<complex<double>> w(2, 1);
  for (uint k = static_cast<uint>(w.size()); k < n; k *= 2) {
    w.resize(n);
    for (uint i = 0; i < k; ++i)
      w[k + i] = exp(complex<double>(0, M_PI * i / k));
  }

  vector<uint> rev(n);
  for (uint i = 0; i < n; ++i)
    rev[i] = (rev[i / 2] | i % 2 * n) / 2;
  for (uint i = 0; i < n; ++i)
    if (i < rev[i])
      swap(a[i], a[rev[i]]);

  for (uint k = 1; k < n; k *= 2)
    for (uint i = 0; i < n; i += k * 2)
      for (uint j = 0; j < k; ++j) {
        auto d = a[i + j + k] * w[j + k];
        a[i + j + k] = a[i + j] - d;
        a[i + j] += d;
      }
}

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  uint N;
  cin >> N;
  vector<int> A(N);
  for (uint i = 0; i < N; ++i)
    cin >> A[i];

  vector<int> diff(N);
  diff[0] = A[0];
  uint nn = 1;
  while (nn <= N)
    nn *= 2;
  vector<complex<double>> buf(nn);
  buf[0] = A[0];
  for (uint i = 1; i < N; ++i) {
    int d = A[i] - A[i - 1];
    diff[i] = d;
    buf[i] = d;
  }
  buf[N] = -A[N - 1];

  fft(buf);
  for (uint i = 0; i < nn; ++i) {
    buf[i] *= conj(buf[i]);
    buf[i] = conj(buf[i]);
  }
  fft(buf);
  for (uint i = 0; i < nn; ++i)
    buf[i] = conj(buf[i]).real() / nn;

  uint max_k = N;
  for (uint i = N - 1; i > 0; --i)
    if (diff[i] > 0) {
      max_k = N - i;
      break;
    }

  vector<pair<lol, uint>> candidates(max_k);
  for (uint lag = 1; lag <= max_k; ++lag)
    candidates[lag - 1] = make_pair(-buf[lag].real() / 5, lag);

  sort(begin(candidates), end(candidates), greater<pair<lol, uint>>());
  lol tweak = (end(candidates) - 1)->first;
  if (tweak < 0)
    for (auto& c : candidates)
      c.first -= tweak;

  uint tries = 100'000 / N * 100;
  lol threshold = 0;
  uint result = 1;
  for (auto& c : candidates) {
    if (tries == 0 || c.first < threshold)
      break;
    uint k = c.second;
    if (k <= result)
      continue;
    bool fail = false;
    vector<int> started_at(N);
    started_at[0] = diff[0];
    for (uint i = 1; i < N; ++i) {
      int ended_at_prev = (i >= k) ? started_at[i - k] : 0;
      started_at[i] = diff[i] + ended_at_prev;
      if (started_at[i] < 0 || (started_at[i] > 0 && i + k > N)) {
        fail = true;
        break;
      }
    }
    if (!fail) {
      result = k;
      threshold = c.first / 10 * 9;
    }
    if (result != 1)
      --tries;
  }
  cout << result << '\n';
}