Fila
Na cerimônia de encerramento da IOI, os competidores formam uma fila à medida que vão chegando ao local. Os competidores são desorganizados e entram na fila perto de seus novos amigos, ou seja, cada competidor escolhe uma posição arbitrária da fila para entrar. Logo na entrada do local há um telão que mostra fotografias e vídeos dos competidores durante a competição. Há uma grande diferença entre as alturas dos competidores, inclusive pelas diferenças de idade, e para que todos possam ver o telão, deve-se evitar que um competidor muito alto fique na frente de um competidor muito baixo, a não ser que esse competidor mais alto esteja longe, mais à frente na fila.
A organização da IOI está monitorando a fila e pediu que você faça um programa que inicialmente receba a descrição da fila inicial (número N de pessoas e suas alturas A1, A2, ... , AN, pela ordem na fila, onde A1 é a altura do primeiro da fila). Em seguida, seu programa deve processar dois tipos de operações:
- na operação tipo 0, seu programa recebe a informação que um novo competidor, de altura H, acabou de entrar na fila, exatamente atrás do I-ésimo competidor na fila (para I = 0 o novo competidor entrou no começo da fila)
- na operação tipo 1, seu programa recebe dois inteiros, I e D, e deve responder a uma consulta: considere a I-ésima pessoa na fila, digamos, P, e determine a posição na fila da pessoa mais próxima de P que está à frente de P e cuja altura é maior do que HI + D (onde HI é a altura de P).
Entrada
A primeira linha da entrada contém um único número inteiro N, indicando o número de pessoas na fila inicial. A segunda linha da entrada contém os N números inteiros A1, A2, ... , AN, as alturas de cada pessoa da fila. A terceira linha contém um único inteiro Q indicando o número de operações. Cada uma das Q linhas seguintes contém três números inteiros números T, I e X, descrevendo uma operação: T indica o tipo da operação, I representa uma posição na fila e X é a altura H do novo competidor (na operação tipo 0) ou o parâmetro D (na operação do tipo 1).Saída
Para cada operação de consulta (tipo 1), seu programa deve produzir uma única linha, contendo um único número inteiro, a resposta à consulta (posição da pessoa na fila), ou 0 caso não haja uma pessoa alta o suficiente.Restrições
- 0 ≤ N ≤ 6 x 105
- 1 ≤ Q ≤ 6 x 105
- 1 ≤ A_i ≤ 109 para todo i, 1 ≤ i ≤ N
- 1 ≤ X ≤ 109
Informações sobre a pontuação
- Em um conjunto de casos de testes somando 40 pontos, N ≤ 2 x 105, Q ≤ 2 x 105 e todas as operações são do tipo 1;
- Em um conjunto de casos de testes somando 80 pontos, N ≤ 2 x 105 e Q ≤ 2 x 105.
Exemplos
Entrada
5 10 5 7 8 2 6 1 5 6 0 1 11 1 6 6 0 0 13 1 6 4 1 6 5 |
Saída
1 2 1 0 |