#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

int T;
int t[30];
int m[100];

int dp[111][30];

void solve(){
    rep(i,T)cin>>t[i];


    fill_n(m,100,1001001);
    int N;cin>>N;
    while(N--){
        int D,M;
        cin>>D>>M;
        D--;
        chmin(m[D],M);
    }


    fill_n(*dp,111*30,1<<25);
    dp[0][0]=0;
    rep(i,100){
        rep(j,T){
            if(t[j]<=m[i]){
                chmin(dp[i+1][(j+1)%T],dp[i][j]);
            }
            chmin(dp[i+1][1%T],dp[i][j]+1);
        }
    }
    int ans=1<<25;
    rep(i,T)chmin(ans,dp[100][i]);
    cout<<ans<<endl;
}

signed main(){
    while(cin>>T,T)solve();
    return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

Peter is a person with erratic sleep habits. He goes to sleep at twelve o'lock every midnight. He gets up just after one hour of sleep on some days; he may even sleep for twenty-three hours on other days. His sleeping duration changes in a cycle, where he always sleeps for only one hour on the first day of the cycle.

Unfortunately, he has some job interviews this month. No doubt he wants to be in time for them. He can take anhydrous caffeine to reset his sleeping cycle to the beginning of the cycle anytime. Then he will wake up after one hour of sleep when he takes caffeine. But of course he wants to avoid taking caffeine as possible, since it may affect his health and accordingly his very important job interviews.

Your task is to write a program that reports the minimum amount of caffeine required for Peter to attend all his interviews without being late, where the information about the cycle and the schedule of his interviews are given. The time for move to the place of each interview should be considered negligible.



Input

The input consists of multiple datasets. Each dataset is given in the following format:

T
t1 t2 ... tT
N
D1 M1
D2 M2
...
DN MN


T is the length of the cycle (1 ≤ T ≤ 30); ti (for 1 ≤ i ≤ T ) is the amount of sleep on the i-th day of the cycle, given in hours (1 ≤ ti ≤ 23); N is the number of interviews (1 ≤ N ≤ 100); Dj (for 1 ≤ j ≤ N) is the day of the j-th interview (1 ≤ Dj ≤ 100); Mj (for 1 ≤ j ≤ N) is the hour when the j-th interview starts (1 ≤ Mj ≤ 23).

The numbers in the input are all integers. t1 is always 1 as stated above. The day indicated by 1 is the first day in the cycle of Peter's sleep.

The last dataset is followed by a line containing one zero. This line is not a part of any dataset and should not be processed.

Output

For each dataset, print the minimum number of times Peter needs to take anhydrous caffeine.

Example

Input

2
1 23
3
1 1
2 1
3 1
0


Output

2

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

int T;
int t[30];
int m[100];

int dp[111][30];

void solve(){
    rep(i,T)cin>>t[i];


    fill_n(m,100,1001001);
    int N;cin>>N;
    while(N--){
        int D,M;
        cin>>D>>M;
        D--;
        chmin(m[D],M);
    }


    fill_n(*dp,111*30,1<<25);
    dp[0][0]=0;
    rep(i,100){
        rep(j,T){
            if(t[j]<=m[i]){
                chmin(dp[i+1][(j+1)%T],dp[i][j]);
            }
            chmin(dp[i+1][1%T],dp[i][j]+1);
        }
    }
    int ans=1<<25;
    rep(i,T)chmin(ans,dp[100][i]);
    cout<<ans<<endl;
}

signed main(){
    while(cin>>T,T)solve();
    return 0;
}
```