dissenting in part:
This case asks whether district courts may incorrectly apply the Sentencing Guidelines in plea agreements as long as they sentence under an agreed cap. Because a primary purpose of the Guidelines was to create uniformity in sentencing, see U.S.S.G. Ch. 1, Pt. A, intro, comment., I must respectfully dissent from Part II-A of a decision that allows such broad license to the district courts in contravention of the Sentencing Commission’s intent.
I. ADDITIONAL FACTS
I first think it important to note a few facts that the majority’s opinion has omitted. The initial plea agreement into which the parties entered contained language stating, “The parties agree that the Sentencing Guidelines will not apply in this case.” The district court, however, said that it could not permit such a statement to be included; the Guidelines, it said, could not be circumvented by plea. As a result, that sentence in the agreement was changed to the following: “The parties agree that the Court may depart upward or downward under the sentencing guidelines.” (emphasis added). The agreement on sentencing thus read:
Defendant may be sentenced to a period of incarceration which is not to exceed 36 months. The parties agree that the Court may depart upward or downward under the sentencing guidelines. The court may, at its discretion, sentence defendant to a period of incarceration of between zero and thirty-six months, including a sentence of probation.
The court then found that the offense level should be 12 and the criminal history category IV, yielding a range of 21-27 months. It departed from the range and imposed a sentence of 36 months based on three reasons: 1) the defendant’s criminal history was under-represented; 2) the parties had stipulated in the plea agreement to a departure of up to 36 months; and 3) the defendant’s connection to the drug transactions was a “close question.”
While there is no doubt that the plea agreement also contained a waiver of appeal, it is instructive to listen to what the district court said at sentencing:
Mr. Bolinger, you have waived appeal rights, including those set forth in 18 U.S.C. § 3742. Out of an abundance of caution, to the full extent that that waiver is in any way not full and complete, I want to advise you that you may have certain limited rights to appeal under that statute.
(emphasis added). Bolinger now appeals his sentence, claiming that the district court improperly set out his offense level and then improperly departed from that level to 36 months. The majority agrees with the government that his appeal is barred by the waiver in the plea agreement. I do not.
II. WAIVER
As the majority explains, whether the appellant waived his statutory right to appeal is a matter of law reviewed de novo. United States v. Navarro-Botello, 912 F.2d 318 (9th Cir.1990).
18 U.S.C. § 3742(a)(2) permits the filing of a notice of appeal if the sentence was imposed “as a result of an incorrect application of the sentencing guidelines.” The majority, however, points to the following language of the plea agreement as evidence that Bolinger is barred from this appeal by his signing of the agreement: “Defendant hereby waives any right to raise and/or appeal any and all motions, defenses, ... and imposition of sentence under Title 18, United States Code, Section 3742.” 1
*482Admittedly, this circuit has held that an express waiver of the right to appeal in a negotiated plea of guilty is valid. United States v. Navarro-Botello, 912 F.2d 318 (9th Cir.1990). In Navarro-Botello we held that since “it is not a due process violation for a defendant to waive constitutional rights as part of a plea bargain, then a defendant’s waiver of a non-constitutional right, such as the statutory right to appeal a sentence, is also waivable.” Id. For purposes of this case, we must focus on the critical caveat we added in that case: “We note, however, that a waiver of the right to appeal would not prevent an appeal where the sentence imposed is not in accordance with the negotiated agreement.” Id. (emphasis added). The whole thrust of Bolinger’s argument is that misapplication of the Guidelines rendered his sentence “not in accordance with the negotiated agreement.” The issue in this case, therefore, is to determine whether he fits within the exception adumbrated by Navarro-Bo-tello.
The majority argues that the sentence did fall within the negotiated agreement because the agreement called for a 36-month “cap” on the sentence, and the term handed down was 36 months. The plea agreement, though, expressly stated that “the court may depart upward or downward under the sentencing guidelines.” (emphasis added). It follows that if the Guidelines were not correctly applied, then the sentence was not under the Guidelines. If this is true, then the court has not adhered to the plea agreement. The majority relies on the fact that the agreement also said that the “court may, at its discretion, sentence defendant to a period of incarceration of between 0 and 36 months.... ” This, it argues, has been done. Yet, just as the court could not simply ignore the Guidelines in sentencing, as it expressly pointed out in response to the initial plea agreement, neither may it improperly apply them.
To subscribe to the majority’s proposed blanket rule enforcing waivers of appeal would give license to the district courts to indulge in some fantastic schemes. For instance, as long as the court stayed under the 36-month cap, it could have arbitrarily determined Bolinger’s offense level to be 40, but then departed downward all the way to 36 months, or stated that the offense level was 2, but a huge upward departure was required. Such flights of fancy are precisely the kind of creative sentencing the Guidelines sought to scuttle. As a prime aim of the Guidelines is to promote uniformity, even in plea agreements, see U.S.S.G. Ch. 6, Pt. B, intro, comment. (“Policy statements governing the acceptance of plea agreements ... are intended to ensure that plea negotiation practices ... do not perpetuate unwarranted sentencing disparity.”), I do not believe we can grant district courts carte blanche so long as they remain under the cap of the plea agreement. The Guidelines must be followed, whether in the context of a plea agreement or not.
Judge Farris himself has pointed out that since “a plea bargain is contractual in nature and is measured by contract-law standards,” “[t]he government will be held to the literal terms of the agreement.” United States v. Read, 778 F.2d 1437, 1441 (9th Cir.1985) (emphasis added) (internal quotations and citations omitted). The government, as drafter of the plea agreement here, should be obliged to fulfill its promise and to ensure that appellant is sentenced under the Guidelines.
Furthermore, policy reasons do not dictate the enforcement of the waiver in this *483case. According to Navarro-Botello: “[P]lea bargaining saves the state time and money,” and it also promotes finality. Id. at 322. While certainly true, these arguments refer far more to the appeal of convictions than sentences. Permitting an appeal of sentence neither deters effective plea bargaining, since appellant is asking only that the court follow the agreement, nor disputes the finality of factual guilt. While great resources both temporal and financial may well be consumed in providing a new trial, considerably less is required for new sentencing.
Vacating the decision here would not, as the majority fears, eviscerate all waivers in plea agreements. See ante at 479. A waiver would clearly be enforceable where the parties themselves calculated a guideline range and explicitly noted their agreement to that range. For example, in Navarro-Botello, where the parties agreed that the range would be 21-25 months and the district court sentenced the defendant to 25 months, we upheld the waiver. Id. at 320. In that instance, if the judge had employed a different range from that on which the parties agreed, it seems clear that the defendant could have successfully appealed.
At bottom, a salient purpose of the Guidelines is to reduce sentencing disparity and to create uniformity. See U.S.S.G. Ch. 1, Pt. A(3). Thus, when an appeal asserts that the district court did not follow the plea agreement because it misapplied the Guidelines, such appeal should not be barred by waiver. Since I believe that appellant may invoke the Navarro-Botello exception, I now address the merits of his claim.
III. APPLICATION OF INCORRECT GUIDELINE
A district court’s interpretation of the Sentencing Guidelines is reviewed de novo. United States v. Howard, 894 F.2d 1085, 1087 (9th Cir.1990).
Bolinger contends that the district court used the wrong guideline in calculating his offense level. By employing the guideline in place at the time of sentencing, instead of using the one on the books at the time of the offense, he states, the court has violated the ex post facto clause.
There is no doubt that the court used the guideline in effect at the time of sentencing, rather than at the time of the offense. Under the original Guidelines, § 2K2.1 was entitled “Receipt, Possession, or Transportation of Firearms and Other Weapons by Prohibited Persons.” See U.S.S.G. App. C. 92 (1990). Previously convicted felons who were convicted of possessing a firearm were given a base offense level of 9 under old § 2K2.1(a). See id. Under amendments effective November 1, 1989, § 2K2.1(a)(2) now sets the offense level at 12 for those convicted of possession of a firearm who had previously been convicted of an “offense punishable by imprisonment for a term exceeding one year....” Id. Since the date of the offense set forth in the indictment is September 19, 1989, the amendments occurred after the offense.
18 U.S.C. § 3553(a)(4) states that sentencing courts should consider “the kinds of sentence and the sentencing range ... as set forth in the guidelines ... and that are in effect on the date the defendant is sentenced.” (emphasis added). That statute, however, as applied in this particular case, violates constitutional protections.
Article I, section 9, clause 3 of the Constitution prohibits Congress from passing any ex post facto law. One example that comes within the purview of the clause is where a “ ‘law changes the punishment, and inflicts a greater punishment, than the law annexed to the crime, when committed.’” Miller v. Florida, 482 U.S. 423, 429, 107 S.Ct. 2446, 2450, 96 L.Ed.2d 351 (1987) (quoting Calder v. Bull, 3 Dall. 386, 390, 1 L.Ed. 648 (1798)). In Miller the Supreme Court prohibited Florida from using its own sentencing guidelines that were revised between Miller’s offense and sentencing, in his case to increase the presumptive sentencing range from Qlz-Qh years to 5V2-7 years. Millers test for whether a criminal law violates the ex post facto clause bears two prongs: “first, the law ‘must be retrospective, that is, it must apply to events occurring before its enact*484ment’; and second, ‘it must disadvantage the offender affected by it.’ ” Id. at 430, 107 S.Ct. at 2451 (quoting Weaver v. Graham, 450 U.S. 24, 29, 101 S.Ct. 960, 964, 67 L.Ed.2d 17 (1981)). The Court held that Florida had offended both prongs by its sentencing of Miller under the revised procedures.
The Supreme Court has not entertained a suit on the retrospective application of amendments to the Sentencing Guidelines, but lower courts have. Our circuit looked at the issue in United States v. Restrepo, 903 F.2d 648 (9th Cir.1990), reh’g en banc ordered, 912 F.2d 1568 (9th Cir.1990). Citing Miller, we noted the above two requirements and added that “ ‘no ex post facto violation occurs if a change does not alter substantial personal rights, but merely changes modes of procedure which do not affect matters of substance.’ ” Id. at 655 (quoting Miller, 482 U.S. at 430, 107 S.Ct. at 2451) (internal quotations omitted). In Restrepo we held that since the specific contested amendments were “not substantive changes but rather clarifications of the Commission’s [earlier] intent,” id. at 656, and “did not alter substantial personal rights,” id., no ex post facto violation occurred.
This case, Bolinger convincingly argues, is different. Because the actual offense level was increased, substantial personal rights were affected. Though there is little law that is directly on point, several district courts have agreed. In United States v. Graham, 731 F.Supp. 944 (C.D.Cal.1990), the court addressed an issue very similar to ours. Believing it was dealing with a case of first impression, this well-reasoned opinion held that where guidelines amended after the offense had called for a higher offense level, application of these, later guidelines violated the ex post facto clause. Where the guideline range increased from 37-46 to 87-108, the court “conclude[d] that the defendant is ‘substantially disadvantaged’ by the application of the higher guidelines.” Id. at 947 (quoting Miller, 482 U.S. at 432-33, 107 S.Ct. at 2452).
Outside our circuit there exist two district court cases even more on point; in fact, one covers the identical situation. In United States v. Landaw, 733 F.Supp. 1256 (N.D.Ind.1990), the defendant was found guilty of possessing a firearm as a felon. The court held that it could not apply the amendment that would have raised the offense level from 9 to 12, exactly the issue here. Without looking at the specific increased incarceration that would occur, the court stated that applying the amendments would violate both prongs of the Miller test because “the law is intended to apply retroactively and the new law provides harsher penalties than did the law in effect at the time of the crime.” Id. at 1259.
Similarly, in United States v. Vastelica, 751 F.Supp. 803 (E.D.Ark.1990), Chief Judge Eisele found an ex post facto clause violation under nearly parallel circumstances. The defendant had been convicted of being a felon in possession of a firearm and of making false statements in connection with the purchase thereof. The court held that sentencing must be based on pre-amendment Guidelines. It quoted extensively from Miller and also mentioned Graham and Landaw. Id. at 806-07. Noting that the proposed sentence under the later amendments would have more than doubled, the court held that “both prongs of the ex post facto analysis are unambiguously met_” Id. at 807. It concluded: “Defendant’s sentence is thus properly calculated under the Guidelines valid at the time the offense was committed.” Id.
In its argument on this issue, the government itself admits that “an amended guideline may not be applied to conduct occurring before the amendment if the amendment clearly disadvantages the defendant.” This is consistent with the position it took during the sentencing hearing, where the government attorney stated that “it’s the Department of Justice’s position that the guidelines would be applied in a way where there is this type of discrepancy which goes to the benefit of the defendant.”
*485In this case the correct range for appellant is 12-18 months, not the 21-27 calculated by the district court. His punishment could double were the latter and not the former employed. Merely sentencing appellant under the cap given by the plea agreement does not palliate misapplying the Guidelines. Just as the government could not have pleaded away the imperative that he be sentenced under the Guidelines, neither can appellant plead away his right to be sentenced correctly under the Guidelines. I would follow both the other district courts that have considered the issue and the government’s own admission and hold that an ex post facto violation does occur where a sentence is retroactively increased by amendment such that it substantially disadvantages the defendant. I would find, therefore, that the district court erred in applying the amended Guidelines, instead of those in effect at the time of the crime.
IV. DEPARTURE
I next briefly examine whether the district court erred in its departure. United States v. Lira-Barraza, 897 F.2d 981, 983 (9th Cir.1990), reh’g en banc granted, 909 F.2d 1370 (9th Cir.1990), set out a five-step standard to review departures from the Guidelines. The district court met the first step by adequately identifying the aggravating or mitigating circumstances that caused the departure: 1) inadequacy of criminal history category; 2) stipulation in plea; and 3) connection to drug transaction.
The second step is to review whether the identified circumstances actually existed. Lira-Barraza, 897 F.2d at 983. Since it is undisputed that appellant did have a prior criminal history and that he agreed to the plea stipulation, the first two circumstances existed. It is not as clear that the third one — the closeness of the connection to the drug transaction — existed. The court itself stated that “there is a serious question whether the government could convict the defendant of [the drug offense].” Further, when the court asked the government at sentencing whether there was “any material evidence concerning the culpability of Mr. Bolinger concerning counts I and II that I didn’t hear at the Bowlin trial,” the government only mentioned an informant’s testimony that it admitted the jury had discredited and to which it had not given any weight. I would hold that the district court clearly erred in finding a “close question” on the connection to the drug offense.
The third step asks whether the particular circumstances were adequately taken into consideration by the Sentencing Commission. Lira-Barraza, 897 F.2d at 983. Such review is conducted de novo. Id. at 984. As to the supposed inadequacy of the criminal history category, § 4A1.3 provides for an upward departure “when the criminal history category significantly under-represents the seriousness of the defendant’s criminal history or the likelihood that the defendant will commit further crimes.” § 4A1.3, p.s. (emphasis added). This is simply not the case here. Appellant was assessed criminal history points for all convictions that occurred within 17 years of the instant offense, except for a DWI conviction. There was no reason for the district court to believe that the criminal history category under-represented his actual criminal history. Furthermore, the district court did not point to any specific acts or convictions to bolster its conclusion. We have held that a conclusory statement that the criminal history is under-represented is insufficient to justify departure. The court must identify specifics. United States v. Michel, 876 F.2d 784, 786 (9th Cir.1989). Therefore, two of the three reasons for departure are now invalid.
The fourth step considers whether the lone remaining circumstance — the stipulation in the plea agreement — should result in departure. Lira-Barraza, 897 F.2d at 983. This is reviewed for abuse of discretion. Id. at 985. Appellant argues that the Guidelines have covered this in § 6B1.2(c)(2), which states that “[i]n the case of a plea agreement that includes a specific sentence ..., the court may accept the agreement if the court is satisfied either that ... (2) the agreed sentence departs from the applicable guideline range for justifiable reasons.” (emphasis add*486ed). If the other two reasons for departure are not “justifiable,” then the existence of the stipulation standing alone is a reed far too weak on which to justify departure. Surely, to argue that departure is justified simply because the plea agreement permitted departure is tautological. There must be concrete grounds for such, and, as has been noted, they do not exist. In any event, if a sentencing court relies on both proper and improper factors in its decision to depart, the sentence must be vacated. United States v. Hernandez-Vasquez, 884 F.2d 1314, 1315-16 (9th Cir.1989). There is no need to examine the fifth step. The district court impermissibly departed.
In sum, I do not believe that this court should place its imprimatur on clear errors in both the determination of the guideline range and in the departure. I would hold the waiver nonbinding and remand for re-sentencing. I, therefore, respectfully DISSENT.
. The government argues that even if we hold the waiver non-binding, we cannot review a claim where there has been a plea agreement with a stipulated sentence that has not been exceeded. The government draws our attention to 18 U.S.C. § 3742(c)(1), which states: "In the case of a plea agreement that includes a specific sentence under Rule 11(e)(1)(C) ... a defendant *482may not file a notice of appeal under paragraph (3) or (4) unless the sentence imposed is greater than the sentence set forth in the agreement." Though Bolinger may well not be able to appeal .under this section, such language cannot nullify § 3742(a)(2), which states that "[a] defendant may file a notice of appeal in the district court for review of an otherwise final sentence if the sentence— ... (2) was imposed as a result of an incorrect application of the sentencing guidelines." See United States v. Smith, 918 F.2d 664, 668-69 (6th Cir.1990) ("Smith is not barred from appealing his sentence under 18 U.S.C. § 3742(c)(1), as the government argues.... Smith may still appeal his sentence under 18 U.S.C. § 3742(a)(1) or (2), which permits appeals of sentences 'imposed in violation of law' and ‘imposed as a result of an incorrect application of the sentencing guidelines!.]' ”).