Index: lib/dataStructure/rmq.cpp
==================================================================
--- lib/dataStructure/rmq.cpp
+++ lib/dataStructure/rmq.cpp
@@ -1,14 +1,14 @@
 //-------------------------------------------------------------
 // Range Minimum Query
 //   O(N log N) construction
-//   O(1) per each query
-//   returns the LEFTMOST/ALL minimum index (I hope)
+//   O(log N) per each query
 //
 // Verified by
 //   - SRM337 Div1 LV2
 //   - SRM431 Div1 LV3
+//   - Codeforces 129 Div1 E
 //-------------------------------------------------------------
 
 template<typename T>
 struct RMQ
 {
@@ -28,18 +28,20 @@
 				if( d[rm[k][x]] > d[rm[k-1][x + (1<<k-1)]] )
 					rm[k][x] = rm[k-1][x + (1<<k-1)];
 		}
 	}
 
-	int operator()(int L, int R) const { // inclusive
+	// min {i in [L,R] | d[i] is minumum among d[L..R]}
+	int operator()(int L, int R) const {
 		int k=0;
 		for(; L+(1<<k) < R-(1<<k)+1; ++k) {}
-		LL i = rm[k][L];
-		LL j = rm[k][R-(1<<k)+1];
+		int i = rm[k][L];
+		int j = rm[k][R-(1<<k)+1];
 		return (d[i]<=d[j] ? i : j);
 	}
 
+	// {i in [L,R] | d[i] is minumum among d[L..R]}
 	vector<int> all(int L, int R) const {
 		vector<int> ans;
 		int minValue = d[(*this)(L, R)];
 		while( L <= R ) {
 			int C = (*this)(L, R);
@@ -48,6 +50,52 @@
 			ans.push_back(C);
 			L = C+1;
 		}
 		return ans;
 	}
+
+	// max {i in [L,R] | d[i]<X}, or -1
+	int rightmost_less_than_X(int L, int R, T X) const {
+		if(L>R) return -1;
+
+		int k=0;
+		for(; L+(1<<k) < R-(1<<k)+1; ++k) {}
+
+		int i = rm[k][L];
+		int j = rm[k][R-(1<<k)+1];
+		if( !(d[i]<X || d[j]<X) )
+			return -1;
+		if( d[j] < X )
+			L = R-(1<<k)+1;
+
+		for(; k; --k) { // Answer is in [L, L+(1<<k))
+			i = rm[k-1][L];
+			j = rm[k-1][L+(1<<k-1)];
+			if( d[j] < X )
+				L += 1<<k-1;
+		}
+		return L;
+	}
+
+	// min {i in [L,R] | d[i]<X}, or -1
+	int leftmost_less_than_X(int L, int R, T X) const {
+		if(L>R) return -1;
+
+		int k=0;
+		for(; L+(1<<k) < R-(1<<k)+1; ++k) {}
+
+		int i = rm[k][L];
+		int j = rm[k][R-(1<<k)+1];
+		if( !(d[i]<X || d[j]<X) )
+			return -1;
+		if( !(d[i] < X) )
+			L = R-(1<<k)+1;
+
+		for(; k; --k) { // Answer is in [L, L+(1<<k))
+			i = rm[k-1][L];
+			j = rm[k-1][L+(1<<k-1)];
+			if( !(d[i] < X) )
+				L += 1<<k-1;
+		}
+		return L;
+	}
 };

ADDED   lib/dataStructure/suffixArray.cpp
Index: lib/dataStructure/suffixArray.cpp
==================================================================
--- lib/dataStructure/suffixArray.cpp
+++ lib/dataStructure/suffixArray.cpp
@@ -0,0 +1,78 @@
+//-------------------------------------------------------------
+// Suffix Array
+//   O(N log N) construction by Larsson-Sadakane
+//    from http://www.prefield.com/algorithm/string/suffix_array.html
+//
+// compute_suffix_array("baca")
+//   = {"aca" < "a$" < "baca" < "ca"} = {1,3,0,2}
+//   EOS is set to be the largest symbol (in SaComp: 0x7fffffff).
+//
+// lcp[0] = -1
+// lcp[i] = lcp of str[sa[i-1]..$] and str[sa[i]..$].
+//
+// Verified by
+//   - Codeforces 129 Div1 E
+//-------------------------------------------------------------
+
+struct SaComp {
+	const int sp, *sr, srlen;
+	SaComp(int sp, const vector<int>& sr) : sp(sp), sr(&sr[0]), srlen(sr.size()) {}
+	bool operator()(int a, int b) const
+	  { return make_pair(sr[a], a+sp<srlen?sr[a+sp]:0x7fffffff)
+	         < make_pair(sr[b], b+sp<srlen?sr[b+sp]:0x7fffffff); }
+};
+
+template<typename RanIt>
+vector<int> compute_suffix_array(RanIt beg, RanIt end)
+{
+	const int N = end - beg;
+
+	vector<int> sa(N);
+	vector<int> sort_rank(beg, end);
+	for(int i=0; i<N; ++i)
+		sa[i] = i;
+
+	sort(sa.begin(), sa.end(), SaComp(0, sort_rank));
+	for(int sorted_prefix=1; sorted_prefix<N; sorted_prefix*=2)
+	{
+		SaComp cmp(sorted_prefix, sort_rank);
+		sort(sa.begin(), sa.end(), cmp);
+
+		vector<int> block_id(N);
+		for(int i=1; i<N; ++i)
+			block_id[i] = block_id[i-1] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
+		for(int i=0; i<N; ++i)
+			sort_rank[sa[i]] = block_id[i];
+	}
+	return sa;
+}
+
+vector<int> inv_sa(const vector<int>& sa)
+{
+	vector<int> isa(sa.size());
+	for(int i=0; i<sa.size(); ++i)
+		isa[sa[i]] = i;
+	return isa;
+}
+
+template<typename RanIte>
+vector<int> longest_common_prefix(RanIte beg, RanIte end, const vector<int>& sa)
+{
+	const int N = sa.size();
+	vector<int> lcp(N);
+	vector<int> inv = inv_sa(sa);
+
+	int len = 0;
+	for(int i=0; i<N; ++i) {
+		int sa_idx = inv[i];
+		if( sa_idx == 0 )
+			lcp[sa_idx] = -1;
+		else {
+			for(int k=sa[sa_idx-1]; i+len<N && k+len<N && *(beg+i+len)==*(beg+k+len);)
+				++len;
+			lcp[sa_idx] = len;
+		}
+		if(len) --len;
+	}
+	return lcp;
+}