using System; using System.Linq; using System.Collections.Generic; namespace yukicoder { class Program { static void Main(string[] args) { int N = int.Parse(Console.ReadLine()); var value = Console.ReadLine().Split(' ').Select(c => int.Parse(c)).ToArray(); var maxPoint = new int[N];//その寿司までに獲得できる最大のおいしさ(その寿司含む) var preDish = new int[N];//直前に食べたすしの添え字 var explorer = new Queue();//幅優先探索 for(int i = 0;i < N;i++) { maxPoint[i] = -1; } maxPoint[0] = value[0]; explorer.Enqueue(0); if(N > 1) { maxPoint[1] = value[1]; explorer.Enqueue(1); } while(explorer.Count > 0) { int v = explorer.Dequeue(); for(int i = 2;i < 4;i++) { if(v + i > N - 1)continue; int point = maxPoint[v] + value[v + i]; if(maxPoint[v + i] == -1) { explorer.Enqueue(v + i); } if(point > maxPoint[v + i]) { maxPoint[v + i] = point; preDish[v + i] = v; } } } int ans = 0; for(int i = 0;i < N;i++) { if(ans < maxPoint[i]) { ans = maxPoint[i]; } } Console.WriteLine(ans); } } }