题目内容

图书馆的书架上摆放着一排共 $n$ 本书，每本书上贴有一个类别标签，标签仅由小写字母表示。图书管理员计划进行 $q$ 次整理工作，每次指定一个连续区间 $[l, r]$，希望把该区间内的所有书都变成同一种类别。他可以任意更改某一本书的标签（换成任意小写字母）。请你帮助管理员计算：对于每次询问，至少需要更换多少本书，才能让指定区间内的所有书标签统一？

字符串的长度 $n$ 与询问的次数 $q$ 均不超过 10^5，所有询问满足 $1 \le l \le r \le n$。下标从 1 开始计数。

输入描述

第一行输入一个整数 $n$。 第二行输入一个长度为 $n$、仅由小写字母组成的字符串，表示初始标签序列。 第三行输入一个整数 $q$。