标签: 括号序

「CodeForces 1239B」 The World Is Just a Programming Task

outputstandard output
This is a harder version of the problem. In this version, 𝑛≤300000.

Vasya is an experienced developer of programming competitions' problems. As all great minds at some time, Vasya faced a creative crisis. To improve the situation, Petya gifted him a string consisting of opening and closing brackets only. Petya believes, that the beauty of the bracket string is a number of its cyclical shifts, which form a correct bracket sequence.