# Given a random string of n left brackets and n right brackets, 
# how often do you need to cut it into two parts and swap
# both sides, to make it "algebraicaly valid"?
rnd_x <- function(n) {
	idx_rb <- sample.int(2*n, n)
	x <- rep(1, 2*n)
	x[idx_rb] <- -1
	x
}

as_br <- function(x) paste0(ifelse(x==1, "(", ")"))

one_x <- function(n) {
	x <- rnd_x(n)
	message(as_br(x))	
	cx <- cumsum(x)
	i <- 0
	while (any(cx<0) && i<2*n) {
		i <- i+1
		br <- which.min(cx)
		x <- c(x[seq(br+1,2*n)], x[1:br])
		message(i,": ", as_br(x))
		cx <- cumsum(x)
	}
	i
}

lapply(1:10, function(n) max(replicate(10^3, one_x(n))))