Дан массив целых чисел \(s_1, s_2, \ldots, s_l\). Каждую секунду, под действием космических лучей, все \(s_i\), такие что \(i=1\) или \(s_i\neq s_{i-1}\), будут одновременно удалены, а оставшиеся части массива будут конкатенированы вместе, чтобы образовать новый массив \(s_1, s_2, \ldots, s_{l'}\).
Определим силу массива как число секунд, которое требуется ему, чтобы стать пустым.
Вам дан массив целых чисел, сжатых в виде \(n\) пар, описывающих массив слева направо. Каждая пара \((a_i,b_i)\) представляет собой \(a_i\) копий \(b_i\), то есть \(\underbrace{b_i,b_i,\cdots,b_i}_{a_i\textrm{ раз}}\).
Для каждого \(i=1,2,\dots,n\) найдите силу последовательности, описываемой первыми \(i\) парами.
Примечание
В первом наборе входных данных, для префикса длины \(4\), изменения будут следующими: \([0,0,1,0,0,0,1,1,1,1,1]\rightarrow[0,0,0,1,1,1,1]\rightarrow[0,0,1,1,1]\rightarrow[0,1,1]\rightarrow[1]\rightarrow[]\), поэтому массив станет пустым через \(5\) секунд.
Во втором наборе входных данных, для префикса длины \(4\), изменения будут следующими:\([6,6,6,6,3,6,6,6,6,0,0,0,0]\rightarrow[6,6,6,6,6,6,0,0,0]\rightarrow[6,6,6,6,6,0,0]\rightarrow[6,6,6,6,0]\rightarrow[6,6,6]\rightarrow[6,6]\rightarrow[6]\rightarrow[]\), поэтому массив станет пустым через \(7\) секунд.