using System; using static System.Console; using System.Linq; using System.Collections.Generic; class Program { static int NN => int.Parse(ReadLine()); static double[] NList => ReadLine().Split().Select(double.Parse).ToArray(); public static void Main() { Solve(); // Test(); // Test2(); } static void Test() { var n = NN; var a = NList; for (var i = 0; i < a.Length; ++i) a[i] *= 0.54 - 0.46 * Math.Cos(2 * Math.PI * i / (n - 1)); var fft = FFT.Calc2(a); WriteLine(string.Join("\n", fft)); // WriteLine(string.Join("\n", a)); } static void Test2() { var f = 100; var fs = 1000; var n = 64; var t = new double[n]; for (var i = 0; i < t.Length; ++i) t[i] = (double)i / fs; var signal = new double[n]; for (var i = 0; i < signal.Length; ++i) signal[i] = Math.Sin(2 * Math.PI * f * t[i]); var window = new double[n]; for (var i = 0; i < window.Length; ++i) window[i] = 0.54 - 0.46 * Math.Cos(2 * Math.PI * i / (n - 1)); var a = new double[n]; for (var i = 0; i < a.Length; ++i) a[i] = signal[i] * window[i]; var fft = FFT.Calc2(a); WriteLine(string.Join("\n", fft)); // WriteLine(string.Join("\n", signal)); // WriteLine(string.Join("\n", window)); } static void Solve() { var n = NN; var a = NList; for (var i = 0; i < a.Length; ++i) a[i] *= 0.54 - 0.46 * Math.Cos(2 * Math.PI * i / (n - 1)); var f = FFT.Calc2(a); var w = new double[] { 261.6, 294.3, 327, 348.8, 392.4, 436, 490.5 }; var s = new string[] { "C4", "D4", "E4", "F4", "G4", "A4", "B4" }; var maxr = 0.0; var ans = ""; for (var i = 0; i < w.Length; ++i) { // var pos = (int)(44100 / w[i]); var pos = (int)w[i]; // WriteLine($"f[{pos}] = {f[pos]} ({f[pos].Magnitude})"); if (maxr < Math.Abs(f[pos].Magnitude)) { maxr = Math.Abs(f[pos].Magnitude); ans = s[i]; } } WriteLine(ans); } class FFT { public static System.Numerics.Complex[] DFT(int[] a) { var xi = new System.Numerics.Complex[a.Length]; for (var i = 0; i < xi.Length; ++i) xi[i] = new System.Numerics.Complex(Math.Cos(i * 2 * Math.PI / xi.Length), Math.Sin(i * 2 * Math.PI / xi.Length)); var ans = new System.Numerics.Complex[a.Length]; for (var i = 0; i < a.Length; ++i) for (var j = 0; j < a.Length; ++j) { ans[i] += a[j] * xi[i * j % xi.Length]; } return ans; } public static System.Numerics.Complex[] Calc(int[] a) { if (a.Length == 0) return new System.Numerics.Complex[0]; var len = 1; while (len < a.Length) len <<= 1; var c = new int[len]; Array.Copy(a, c, a.Length); var dp = new System.Numerics.Complex[len]; var xi = new System.Numerics.Complex[len]; for (var i = 0; i < xi.Length; ++i) xi[i] = new System.Numerics.Complex(Math.Cos(i * 2 * Math.PI / len), Math.Sin(i * 2 * Math.PI / len)); _Calc(dp, xi, c); return dp; } static void _Calc(System.Numerics.Complex[] dp, System.Numerics.Complex[] xi, int[] c) { if (dp.Length == 1) { dp[0] = c[0]; return; } var len = dp.Length / 2; var dp0 = new System.Numerics.Complex[len]; var dp1 = new System.Numerics.Complex[len]; var c0 = new int[len]; var c1 = new int[len]; var x0 = new System.Numerics.Complex[len]; for (var i = 0; i < len; ++i) { c0[i] = c[i * 2]; c1[i] = c[i * 2 + 1]; x0[i] = xi[i * 2]; } _Calc(dp0, x0, c0); _Calc(dp1, x0, c1); for (var i = 0; i < dp.Length; ++i) { dp[i] = dp0[i % len] + xi[i] * dp1[i % len]; } } public static System.Numerics.Complex[] Calc2(double[] a) { if (a.Length == 0) return new System.Numerics.Complex[0]; var dp = new System.Numerics.Complex[a.Length]; for (var i = 0; i < a.Length; ++i) dp[i] = a[i]; _Calc2(dp); return dp; } static void _Calc2(System.Numerics.Complex[] dp) { if (dp.Length == 1) return; var len = dp.Length / 2; var dp0 = new System.Numerics.Complex[len]; var dp1 = new System.Numerics.Complex[len]; for (var i = 0; i < len; ++i) { dp0[i] = dp[i * 2]; dp1[i] = dp[i * 2 + 1]; } _Calc2(dp0); _Calc2(dp1); var now = new System.Numerics.Complex(1, 0); var zeta = new System.Numerics.Complex(Math.Cos(2 * Math.PI / dp.Length), Math.Sin(2 * Math.PI / dp.Length)); for (var i = 0; i < dp.Length; ++i) { dp[i] = dp0[i % len] + now * dp1[i % len]; now *= zeta; } } } // 畳み込みを mod で計算する class ConvolutionCalculator { int mod; public ConvolutionCalculator(int mod) { this.mod = mod; } public int[] Calc(long[] a, long[] b) { var _a = new int[a.Length]; var _b = new int[b.Length]; for (var i = 0; i < a.Length; ++i) _a[i] = (int)(a[i] % mod); for (var i = 0; i < b.Length; ++i) _b[i] = (int)(b[i] % mod); return Calc(_a, _b); } public int[] Calc(int[] a, int[] b) { var n = a.Length; var m = b.Length; if (n == 0 || m == 0) { return new int[0]; } if (Math.Min(n, m) <= 100) { return ShortComvolution(a, b); } var z = 1 << CeilPow(n + m - 1); var za = new int[z]; var zb = new int[z]; Array.Copy(a, za, a.Length); Array.Copy(b, zb, b.Length); InitButterfly(); Butterfly(za); Butterfly(zb); for (var i = 0; i < z; ++i) { za[i] = (int)((long)za[i] * zb[i] % mod); } ButterflyInv(za); var iz = PowMod(z, mod - 2, mod); var ans = new int[n + m - 1]; for (var i = 0; i < ans.Length; ++i) { ans[i] = (int)((long)za[i] * iz % mod); } return ans; } int[] ShortComvolution(int[] a, int[] b) { var ans = new int[a.Length + b.Length - 1]; for (var i = 0; i < a.Length; ++i) { for (var j = 0; j < b.Length; ++j) { ans[i + j] = (int)((ans[i + j] + (long)a[i] * b[j] % mod) % mod); } } return ans; } int[] sume = new int[30]; int[] sumie = new int[30]; void InitButterfly() { var g = PrimitiveRoot(mod); var es = new int[30]; var ies = new int[30]; var cnt2 = BSF(mod - 1); var e = PowMod(g, mod - 1 >> cnt2, mod); var ie = PowMod(e, mod - 2, mod); for (var i = cnt2; i >= 2; --i) { es[i - 2] = e; ies[i - 2] = ie; e = (int)((long)e * e % mod); ie = (int)((long)ie * ie % mod); } var now = 1L; var inow = 1L; for (var i = 0; i < cnt2 - 2; ++i) { sume[i] = (int)(es[i] * now % mod); now = now * ies[i] % mod; sumie[i] = (int)(ies[i] * inow % mod); inow = inow * es[i] % mod; } } void Butterfly(int[] a) { var h = CeilPow(a.Length); for (var ph = 1; ph <= h; ++ph) { var w = 1 << (ph - 1); var p = 1 << (h - ph); var now = 1L; for (var s = 0; s < w; ++s) { var offset = s << (h - ph + 1); for (var i = 0; i < p; ++i) { var l = a[i + offset]; var r = (int)(a[i + offset + p] * now % mod); a[i + offset] = (l + r) % mod; a[i + offset + p] = (int)((long)mod + l - r) % mod; } now = now * sume[BSF(~(uint)s)] % mod; } } } void ButterflyInv(int[] a) { var h = CeilPow(a.Length); for (var ph = h; ph >= 1; --ph) { var w = 1 << (ph - 1); var p = 1 << (h - ph); var inow = 1L; for (var s = 0; s < w; ++s) { var offset = s << (h - ph + 1); for (var i = 0; i < p; ++i) { var l = a[i + offset]; var r = a[i + offset + p]; a[i + offset] = (l + r) % mod; a[i + offset + p] = (int)(((long)mod + l - r) * inow % mod); } inow = inow * sumie[BSF(~(uint)s)] % mod; } } } static int PowMod(int n, int p, int mod) { long _n = n % mod; var _p = p; var result = 1L; if ((_p & 1) == 1) { result *= _n; } while (_p > 0) { _n = _n * _n % mod; _p >>= 1; if ((_p & 1) == 1) { result = (result * _n) % mod; } } return (int)result; } static int PrimitiveRoot(int m) { if (m == 2) return 1; if (m == 167772161) return 3; if (m == 469762049) return 3; if (m == 754974721) return 11; if (m == 998244353) return 3; if (m == 1000000007) return 5; var divs = new int[20]; divs[0] = 2; var cnt = 1; var x = (m - 1) / 2; while (x % 2 == 0) x /= 2; for (var i = 3; (long)i * i <= x; i += 2) { if (x % i == 0) { divs[cnt++] = i; while (x % i == 0) x /= i; } } if (x > 1) divs[cnt++] = x; for (var g = 2;; ++g) { var ok = true; for (var i = 0; i < cnt; ++i) { if (PowMod(g, (m - 1) / divs[i], m) == 1) { ok = false; break; } } if (ok) return g; } } static int CeilPow(int n) { var x = 0; while ((1U << x) < (uint)n) x++; return x; } static int BSF(int n) { if (n == 0) return 0; var count = 0; while ((n & 1) == 0) { ++count; n >>= 1; } return count; } static int BSF(uint n) { if (n == 0) return 0; var count = 0; while ((n & 1) == 0) { ++count; n >>= 1; } return count; } public long[] ConvolutionLL(long[] a, long[] b) { if (a.Length == 0 && b.Length == 0) return new long[0]; const ulong MOD1 = 754_974_721; const ulong MOD2 = 167_772_161; const ulong MOD3 = 469_762_049; const ulong M2M3 = 78_812_994_116_517_889; const ulong M1M3 = 354_658_471_880_163_329; const ulong M1M2 = 126_663_740_442_542_081; const ulong M1M2M3 = 560_135_205_046_714_369; const ulong i1 = 190_329_765; const ulong i2 = 58_587_104; const ulong i3 = 187_290_749; ulong[] offset = new ulong[] { 0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3 }; var c1 = new ConvolutionCalculator((int)MOD1).Calc(a, b); var c2 = new ConvolutionCalculator((int)MOD2).Calc(a, b); var c3 = new ConvolutionCalculator((int)MOD3).Calc(a, b); var ans = new long[a.Length + b.Length - 1]; for (var i = 0; i < ans.Length; ++i) { ulong x = 0; x += (ulong)c1[i] * i1 % MOD1 * M2M3; x += (ulong)c2[i] * i2 % MOD2 * M1M3; x += (ulong)c3[i] * i3 % MOD3 * M1M2; var diff = c1[i] - SafeMod((long)x, (long)MOD1); if (diff < 0) diff += (long)MOD1; x -= offset[diff % 5]; ans[i] = (long)x; } return ans; } static long SafeMod(long a, long b) { a %= b; if (a < 0) a += b; return a; } } }