/**
* Two pointer algorithm
* O(2*n)
* See:
* http://codeforces.com/contest/676/problem/C
* http://codeforces.com/contest/580/problem/B
*
* @param n maximum right bound
* @param f given an interval returns if it is acceptable
* f must be monotonic i.e. for all super-interval j of i, f(j) implies f(i)
*
* @return List of all intervals in [0, n) at which f is acceptable
*/
def validIntervals(n: Int)(f: (Int, Int) => Boolean): Iterator[(Int, Int)] = {
val it = new Iterator[Option[(Int, Int)]] {
var l, r = 0
override def hasNext = r < n
override def next() = {
if(f(l, r)) {
r += 1
Some((l, r - 1))
} else {
if(l < r) l += 1 else r += 1
None
}
}
}
it.flatten
}