{"raw_statement":[{"iden":"problem statement","content":"You are given a sequence $a = {a_1, ..., a_N}$ with all zeros, and a sequence $b = {b_1, ..., b_N}$ consisting of $0$ and $1$. The length of both is $N$.\nYou can perform $Q$ kinds of operations. The $i$\\-th operation is as follows:\n\n*   Replace each of $a_{l_i}, a_{l_i + 1}, ..., a_{r_i}$ with $1$.\n\nMinimize the hamming distance between $a$ and $b$, that is, the number of $i$ such that $a_i \\neq b_i$, by performing some of the $Q$ operations."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 200,000$\n*   $b$ consists of $0$ and $1$.\n*   $1 \\leq Q \\leq 200,000$\n*   $1 \\leq l_i \\leq r_i \\leq N$\n*   If $i \\neq j$, either $l_i \\neq l_j$ or $r_i \\neq r_j$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$b_1$ $b_2$ $...$ $b_N$\n$Q$\n$l_1$ $r_1$\n$l_2$ $r_2$\n$:$\n$l_Q$ $r_Q$"},{"iden":"sample input 1","content":"3\n1 0 1\n1\n1 3"},{"iden":"sample output 1","content":"1\n\nIf you choose to perform the operation, $a$ will become ${1, 1, 1}$, for a hamming distance of $1$."},{"iden":"sample input 2","content":"3\n1 0 1\n2\n1 1\n3 3"},{"iden":"sample output 2","content":"0\n\nIf both operations are performed, $a$ will become ${1, 0, 1}$, for a hamming distance of $0$."},{"iden":"sample input 3","content":"3\n1 0 1\n2\n1 1\n2 3"},{"iden":"sample output 3","content":"1"},{"iden":"sample input 4","content":"5\n0 1 0 1 0\n1\n1 5"},{"iden":"sample output 4","content":"2\n\nIt may be optimal to perform no operation."},{"iden":"sample input 5","content":"9\n0 1 0 1 1 1 0 1 0\n3\n1 4\n5 8\n6 7"},{"iden":"sample output 5","content":"3"},{"iden":"sample input 6","content":"15\n1 1 0 0 0 0 0 0 1 0 1 1 1 0 0\n9\n4 10\n13 14\n1 7\n4 14\n9 11\n2 6\n7 8\n3 12\n7 13"},{"iden":"sample output 6","content":"5"},{"iden":"sample input 7","content":"10\n0 0 0 1 0 0 1 1 1 0\n7\n1 4\n2 5\n1 3\n6 7\n9 9\n1 5\n7 9"},{"iden":"sample output 7","content":"1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}