解题思路

问题分析

给定长度为 $n$ 的字符串 $S$，包含小写字母。每个查询给出区间 $[l, r]$，要求将区间内的所有字符都变成同一个字母，最少需要修改多少个字符？

本质上就是在区间 $[l, r]$ 中，选一个出现次数最多的字母，将其他字符都改为该字母。若该字母出现次数为 $\text{maxCnt}$，区间长度为 $\text{len}=r-l+1$，则最少修改次数为 $\text{ans} = \text{len}$ - $\text{maxCnt}.$

数据结构与预处理

• 构造一个前缀和数组 cnt[i][c]，表示 $S[1..i]$ 中字母 c 的出现次数。

题目内容

小红有一个长度为n 的字符串$S_1S_2···Sn$，字符串中只包含小写字母，每个字母代表一种颜色。

小红有$q$次询问，每次询问如果将区间$[l,r]$染成相同的颜色，至少需要修改多少个字母，才能使得区间$[l,r]$染成相同的颜色。请你帮助小红解决这个问题。

输入描述

第一行输入一个整数$n(1≤n≤100000)$，表示字符串$s$的长度。

第二行输入一个长度为$n$、且仅由小写字母构成的字符串$s$，表示小红的字符串。

第三行输入一个整数$q(1≤q≤100000)$，表示询问的次数。

接下来$q$行，每行输入两个整数$l,r(1≤l≤r≤n)$,表示一次询问的区间。

输出描述

对于每一个询问，在一行上输出一个整数，表示询问的答案。

样例1

输入

5
abbdf
3
1 3
2 5
2 3

输出

1
2
0

说明

在本题中，我们以$1$作为下标的开始