Ilya va so'rovlar

Faqat . va # belgilaridan iborat $s_1 s_2 \ldots s_n$ satr berilgan. Har bir $(l, r)$ so'rov uchun $l \le i < r$ va $s_i = s_{i+1}$ shartini qanoatlantiradigan $i$ lar sonini toping.

Birinchi qatorda $s$ satri ($2 \le n \le 10^5$). Ikkinchi qatorda $m$ ($1 \le m \le 10^5$). Keyingi $m$ ta qatorda $l$ va $r$ ($1 \le l < r \le n$).

Har bir so'rov uchun alohida qatorda bitta son.

$c_i = 1$, agar $s_i = s_{i+1}$ bo'lsa, aks holda $0$ deb belgilang. Javob — $c_l + \ldots + c_{r-1}$, ya'ni $c$ ning prefiks yig'indisi bilan $p_{r-1} - p_{l-1}$. Indekslarga e'tibor bering: $i = r$ hisobga olinmaydi.

Ikkinchi misolning birinchi so'rovida (#..) faqat $s_2 = s_3$ — javob $1$.

Manba: Codeforces, 313B-masala.