Алаңда бір қатарда \(n\) орын бар, олар \(1\)-ден \(n\)-ға дейін нөмірленген. Бастапқыда әр позицияда дәл бір плитка болды, бірақ уақыт өте плиткалар орындарын ауыстырды. Енді кейбір жерлерде екі плитка, кейбірінде — бір плитка, ал кейбірінде — нөл плитка бар. Плиткалардың жалпы саны әлі де \(n\)-ға тең.

Жақында \([l, r]\) аралығында маңызды іс-шара өтеді, сондықтан бұл жерді бірінші кезекте жөндеу қажет. Жөндеу аяқталды деп есептеледі, егер \(l\)-ден \(r\)-ға дейінгі әр позицияда (қоса алғанда) дәл бір плитка болса. Жұмысшы бастапқыда \(l-1\) позициясында тұрады. Бір секундта ол көрші позицияға ауыса алады. Плиткалар орналасқан позицияда ол бір плитканы ала алады (уақыт жұмсалмайды). Ол өзімен алып жүрген плитканы ағымдағы позицияға қоя алады (уақыт жұмсалмайды). Бір уақытта ол тек бір плитканы ғана алып жүре алады.

\([l, r]\) аралығын жөндеу үшін тек \(l\)-ден \(r\)-ға дейінгі позицияларда орналасқан плиткаларды пайдалануға болады. \([l, r]\) аралығында дәл \(r - l + 1\) плитка бар екендігі кепілдендірілген. Жөндеу аяқталғаннан кейін жұмысшы \(l-1\) позициясына қайта оралуы керек.

\([l, r]\) аралығын жөндеуге қажетті минималды уақытты табыңыз.

Енгізу

Бірінші жолда бүтін сан \(n\) (\(1 \leq n \leq 10^6\)) — позициялардың саны.

Екінші жолда \(n\) бүтін саны \(a_1, a_2, \ldots, a_n\) (\(0 \leq a_i \leq 2\)) — әр позициядағы плиткалардың саны. \(\sum_{i=1}^{n} a_i = n\) екендігі кепілдендірілген.

Үшінші жолда бүтін сан \(q\) (\(1 \leq q \leq 10^6\)) — сұраулардың саны.

Келесі \(q\) жолдың әрқайсысы екі бүтін сан \(l_j, r_j\) (\(1 \leq l_j \leq r_j \leq n\)) — жөндеу үшін аралықтың шекаралары. \(\sum_{i=l_j}^{r_j} a_i = r_j - l_j + 1\) екендігі кепілдендірілген.

Шығару

Әр сұрау үшін жөндеуге қажетті минималды уақытты шығарыңыз.

Мысалдар

Енгізу 1

13
1 2 2 2 0 0 0 2 2 0 1 1 0
4
1 7
11 12
4 9
7 11

Жауап 1

22
0
14
8

Ескертпелер

4-ші сұрау үшін (отрезок \([7, 11]\)):

Бастапқы жағдай: позиция 7 — 0 плитка, позиция 8 — 2 плитка, позиция 9 — 2 плитка, позиция 10 — 0 плитка, позиция 11 — 1 плитка.

Жұмысшы 6-шы позициядан бастайды. Плиткаларды 7-ден 11-ге дейінгі әр позицияда дәл бір плитка болатындай етіп жылжыту керек.

8 секундта оңтайлы шешім:

• 8-ші позицияға жылжу (2 секунд)

• 8-ші позициядан плитканы алу (0 секунд)

• 10-шы позицияға жылжу (2 секунд)

• 10-шы позицияға плитканы қою (0 секунд)

• 9-шы позицияға жылжу (1 секунд)

• 9-шы позициядан плитканы алу (0 секунд)

• 7-ші позицияға жылжу (2 секунд)

• 7-ші позицияға плитканы қою (0 секунд)

• 6-шы позицияға қайту (1 секунд)

Жалпы уақыт: \(2 + 2 + 1 + 2 + 1 = 8\) секунд.